Является ли топологический вид исходного графа таким же, как dfs транспонированного графа

Question

У меня есть интуиция, что топо-сортировка исходного графа такая же, как у dfs транспонированного графа (перевернуть все ребра)

 A -> B -> C
 D -> B

топо-сортировка [D, A, B, C] или [A, D, B, C]

Если я переставлю график (переверну все ребра)

  C -> B -> A   
       B -> D

, то dfs также даст [D, A, B, C ] или [A, D, B, C]

Пожалуйста, я не могу математически доказать / опровергнуть это. Если предложение неверно, полезен контрпример

Answer 1

Это не совпадение - вы только что заново открыли общий алгоритм поиска топологических упорядочений!

Один алгоритм, который обычно используется для поиска топологических упорядочений, выполняет DFS и записывает узлы в обратный порядок их окончания времени. (Попробуйте!) Ваш алгоритм по сути эквивалентен этому.

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