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

Question

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

Они такие же или разные вещи?

Answer 1

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

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

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

В топологической сортировке мы работаем над partially ordered set, но при нормальной сортировке мы работаем над total ordered set.

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