Топологическая сортировка пытается отсортировать вершины или ребра?

Всем счастливой пасхи.

В настоящее время я изучаю топологическую сортировку и задаюсь вопросом о том, какая топологическая сортировка пытается сортировать на самом деле.

В Руководстве по разработке алгоритмов топологическая сортировка описывается следующим образом:

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

Эта смелая часть меня смущает. Так сортирует ли топологическая сортировка вершины или все ориентированные ребра?

Возьмем пример, который тоже есть в книге.

DAG

Итак, для указанного выше DAG мы можем получить топологическую сортировку (G, A, B, C, F, E, D).

Я могу понять такого рода. Сортированы не только вершины, но и ребра, то есть G-> A-> B-> C-> F-> E-> D, это соответствует приведенному выше описанию книги ADM: all directed edges go from left to right

Но что, если я удалю край B-> C? Полученный граф по-прежнему является DAG, но будет ли топологическая сортировка по-прежнему (G, A, B, C, F, E, D) ?

Если да, то я думаю, что края не сортируются, поскольку A-> B-> C больше не существует, вместо этого это A-> B и A-> C. Итак, это все еще актуальная топологическая сортировка? Можем ли мы по-прежнему считать (G, A, B, C, F, E, D) допустимой сортировкой, даже если A является родителем B и C?

Спасибо


graph algorithm data-structures depth-first-search topological-sort
person Jackson Tale    schedule 08.04.2012    source источник

Ответы (1)


arrow_upward
9
arrow_downward

Вы можете думать об этом как о порядке элементов.

пусть v1, v2, ..., vn - элементы. и пусть ребро (vi,vj) обозначает это vi<vj. топологическая сортировка гарантирует, что после сортировки: для каждого vi и для каждого vj такого, что i < j, vj не больше vi

Или в других обозначениях: предположим, что (vi,vj) указывает, что vj зависит от vi, топологическая сортировка гарантирует, что каждый элемент «не зависит» от каких-либо элементов, которые появляются после него в сортировке.

Так сортирует ли топологическая сортировка вершины или все ориентированные ребра?

топологическая сортировка сортирует вершины, а не ребра. Он использует ребра в качестве ограничений для сортировки вершин.

Но что, если я уберу край B-> C?

да, каждое добавленное вами ребро, просто добавьте ограничение. Обратите внимание, что может быть более одного допустимого решения для топологической сортировки [например, для графа без ребер любая перестановка является допустимым решением]. удаление ограничения делает любое предыдущее решение, которое «решает более сложную проблему», по-прежнему выполнимым.

Можем ли мы по-прежнему считать (G, A, B, C, F, E, D) допустимой сортировкой, даже если A является родителем B и C?

С этим нет проблем! A стоит перед B, C в топологической сортировке, поэтому нет проблем, что это их отец.

Надеюсь, это проясняет ситуацию.

person amit    schedule 08.04.2012
comment
Итак, по вашему описанию, если я удалю B- ›C, то B должно быть до C или после C? Потому что мы больше не знаем, меньше ли B, чем C, или нет - person Jackson Tale; 08.04.2012
comment
@JacksonTale: Если вы удалите B->C, оба решения станут возможными! [если я не пропустил какой-то край], как я уже упоминал, может быть несколько решений топологической сортировки. - person amit; 08.04.2012
comment
Спасибо, amit, теперь ваша редакция позволила мне понять намного яснее. - person Jackson Tale; 08.04.2012
comment
@JacksonTale - многие группы DAG описывают наборы, которые упорядочены только частично (POSET), и поэтому есть более возможные топологические сортировки. В вашем примере, если вы удалите B- ›C, то G-› A- ›C-› F- ›E-› D все равно должны появиться в этом порядке. B теперь ограничен только ребрами от A до D и поэтому может появляться где угодно между ними; приводя к 4 различным возможным видам - person voidengine; 08.04.2012
comment
@pjotr, действительно, спасибо. Ваша информация о POSET мне еще больше помогла. - person Jackson Tale; 08.04.2012