Как изменить DFS на топологическую сортировку

#algorithm #data-structures #depth-first-search #topological-sort

#алгоритм #структуры данных #поиск в глубину #топологическая сортировка

Вопрос:

Я сам читал о топологической сортировке, но я не могу преобразовать псевдокод DFS в TS

Может кто-нибудь объяснить мне, как я могу изменить этот DFS для выполнения топологической сортировки

Кто-нибудь может сказать мне, что время до и после для этого графика при использовании DFS предполагает, что начальная вершина равна 10

1. Я рассчитал время до и после: Вершина 10: Pre = 1 и Post = 2 Вершина 5: Pre = 3 и Post = 10 Вершина 11: Pre = 4 и Post = 9 Вершина 2: Pre = 5 и Post = 8 Вершина 9: Pre = 6 и Post =7 Вершина 7: Pre = 11 и Post = 14 Вершина 8: Pre = 12 и Post = 13 Вершина 3: Pre = 15 и Post = 16 Порядок топологической сортировки: 3,7,8,5,11,2,9,10 (изменение времени публикации)

Ответ №1:

посмотрите на переменную time = 0 в строке 4, это ваша переменная для отслеживания номеров до / после. строка 10 присваивает значение time узлу, который находится visited — u.f Теперь все узлы имеют атрибут f с соответствующими значениями времени. Это номера почтовых заказов. Вам нужно упорядочить узлы в порядке убывания этих чисел. Это ваша топологическая сортировка.

1. Порядок топологической сортировки: 3,7,8,5,11,2,9,10 (изменение времени публикации) Это мой заказ, и в первом комментарии я также написал время до / после. Хотите ли вы подтвердить мои ответы?