В чем разница между сортировкой и топологической сортировкой?

Question

В чем разница между сортировкой и топологической сортировкой?

Это одно и то же или разное?

Answer 1

На абстрактном уровне они связаны: как говорят Саид и Стефан, это разница между полным заказом и частичным заказом. Это фантастически краткое описание, но иногда оно бесполезно, когда вы учитесь.

Общий порядок означает, что при отсутствии повторов, когда вы что-то сортируете, вы получите один уникальный правильный ответ. Если вы сортируете 3, 6, 2 в порядке возрастания, вам лучше получить один ответ: 2, 3, 6.

Частичный порядок немного слабее. Каноническим примером является порядок, в котором вы надеваете свою одежду: вы можете надеть свои шорты, затем штаны, затем носки, затем туфли. Это действительный заказ. Или вы могли бы сделать шорты, носки, брюки, обувь. Но интуитивно, вы не можете делать шорты, брюки, обувь, носки. Носить носки за туфлями не имеет смысла.

Чтобы формализовать этот пример одевания, вы обычно показываете граф зависимостей с действиями («надеть ботинки») в качестве узлов и направленными дугами, показывающими, какой узел должен предшествовать другим узлам. Топологическая сортировка - это порядок всех узлов в графе, подобный тому, который учитывает дуги. То есть, если от носков до туфель есть дуга, то носки лучше перед туфлями в порядке.

Итак, опять же, на абстрактном уровне, они связаны. Но они абсолютно НЕ одно и то же.

Answer 2

В топологической сортировке мы работаем с частично упорядоченным множеством , но при обычной сортировке мы работаем с общим упорядоченным множеством .

В топологической сортировкевозможно, нет никакой связи между парой элементов множества, как в ориентированных графах, между некоторыми узлами нет никакой связи.При обычной сортировке все пары элементов множества имеют отношение.Например, в наборе чисел у нас есть отношение <,>, = между всеми парами, поэтому оно упорядочено по сумме.

Answer 3

Топологическая сортировка обычно относится к нахождению общего порядка, который соответствует некоторому частичному порядку, например, отношение достижимости в ориентированном ациклическом графе.

Answer 4

Если общий заказ доступен, каждый объект можно сравнить с каждым объектом. В этом случае вы можете сортировать по. этот порядок. Примерами являются целые числа относительно. > (или <, или <=, ...) или строка в отношении. лексикографический порядок. При наличии общего заказа возможна сортировка. </p>

Если доступен только частичный порядок, не каждый объект можно сравнить с любым другим объектом. Доступна только связь между определенными объектами. Примером являются зависимости между модулями компиляции. Топологическая сортировка - это задача найти порядок объектов таким образом, чтобы соблюдается частичный порядок (например, путем компиляции модулей, которые зависят от некоторого другого модуля после этих модулей). Здесь возможны несколько решений (т. Е. Упорядочения): если A зависит от B и есть какой-то другой блок C, возможными последовательностями компиляции являются B, A, C и C, A, B (каждая последовательность, где A компилируется до B).