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

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

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

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

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

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

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

A DAG

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

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

Но что, если я удалю ребро B->C?Результирующий граф по-прежнему будет DAG, но будет ли топологическая сортировка по-прежнему (G, A, B, C, F, Е, Г)?

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

Спасибо

6
задан svick 8 April 2012 в 11:44
поделиться