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

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

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

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


algorithm data-structures depth-first-search topological-sort
person Awais Younis    schedule 09.12.2020    source источник
comment
Время до и после, которое я рассчитал, таково: Вершина 10: до = 1 и после = 2 Вершина 5: до = 3 и после = 10 Вершина 11: до = 4 и после = 9 Вершина 2: до = 5 и после = 8 Вершина 9: до = 6 и после = 7 Вершина 7: до = 11 и после = 14 Вершина 8: до = 12 и после = 13 Вершина 3: до = 15 и после = 16 Топологический порядок сортировки: 3,7, 8,5,11,2,9,10 (Обратное время публикации)   -  person Awais Younis    schedule 09.12.2020

Ответы (1)


arrow_upward
0
arrow_downward

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

person ameet chaubal    schedule 13.12.2020
comment
Топологический порядок сортировки: 3,7,8,5,11,2,9,10 (обратное время публикации) Это мой порядок, и в первом комментарии я также написал время до/после публикации. Хотите подтвердить мои ответы? - person Awais Younis; 14.12.2020