Топологическая сортировка - это результат, который вы получаете, когда сортируете дерево в порядке уменьшения времени завершения. Это означает, что вы запускаете алгоритм поиска в глубину, и после его завершения у вас будет два набора значений: время обнаружения и время завершения. Время окончания, отсортированное в обратном порядке, будет генерировать топологически отсортированный список.
DFS начинает обход дерева в вершине A. Поскольку оно было обнаружено, мы помечаем его цифрой 1. Число 1 используется для обозначения того, что оно было обнаружено первым.
Алгоритм проверяет все непосещенные узлы из вершины A. Вершина A соединяется с непосещенными узлами B и C. Затем алгоритм DFS посещает вершину B. Вершина B помечается как посещенная и получает время обнаружения 2.
Алгоритм проверяет все непосещенные узлы из вершины B. Вершина B соединяется с непосещенными узлами C и D. Затем алгоритм DFS посещает вершину C. Вершина C помечается как посещенная и получает время обнаружения 3.
Алгоритм проверяет все непосещенные узлы из вершины C. Вершина C соединяется с непосещенными узлами E и F. Затем алгоритм DFS посещает вершину E. Вершина E помечается как посещенная и получает время обнаружения 4.
Вершина E не имеет дополнительных ребер, которые связаны с непосещенными узлами. Он возвращается к вершине C. При возврате вершина E получает время завершения 5. Время завершения, 5, отображается после времени обнаружения, равного 4.
Алгоритм снова проверяет все непосещенные узлы из вершины C. Вершина C соединяется с непосещенным узлом F. Затем алгоритм DFS посещает вершину F. Вершина F помечается как посещенная и получает время обнаружения 6.
Вершина F не имеет дополнительных ребер, которые связаны с непосещенными узлами. Он возвращается к вершине C. При возврате вершина F получает время завершения 7. Время завершения, 7, отображается после времени обнаружения, равного 6.
Вершина C не имеет дополнительных ребер, которые связаны с непосещенными узлами. Он возвращается к вершине B. При возврате вершина C получает время завершения 8. Время завершения, 8, отображается после времени обнаружения, равного 3.
Алгоритм снова проверяет все непосещенные узлы из вершины B. Вершина B соединяется с непосещенным узлом D. Затем алгоритм DFS посещает вершину D. Вершина D помечается как посещенная и получает время обнаружения 9.
Вершина D не имеет дополнительных ребер, которые связаны с непосещенными узлами. Он возвращается к вершине B. При возврате вершина D получает время завершения 10. Время завершения, 10, отображается после времени обнаружения, равного 9.
Вершина B не имеет дополнительных ребер, которые связаны с непосещенными узлами. Он возвращается к вершине A. При возврате вершина B получает время завершения 11. Время завершения, 11, отображается после времени обнаружения, равного 2.
Вершина A не имеет дополнительных ребер, которые связаны с непосещенными узлами. Он пытается вернуться, но не имеет дополнительных узлов для возврата. При возврате вершина A получает время завершения, равное 12. Время завершения, 12, отображается после времени обнаружения, равного 1. Алгоритм DFS завершается.
Чтобы получить список времен обнаружения, вы размещаете элементы в порядке возрастания времени обнаружения.
Чтобы получить топологически отсортированный список, вы размещаете элементы в порядке убывания времени окончания. A был последним элементом, который был помечен как завершенный, поэтому он идет первым, затем идет B, а затем D. Хотя первые два элемента были одинаковыми в обоих списках, элемент 3 изменяется с C на D. Затем была отмечена вершина C. как завершенный, за которыми следуют вершины F и E. Это завершает топологически отсортированный список.
Если вам понравилось то, что вы прочитали, моя книга Иллюстративное введение в алгоритмы охватывает этот алгоритм и многое другое.
