Есть ли разница между dfs и топологической сортировкой? Можно ли добиться топологического упорядочения без использования dfs?

Я пытался написать код для обнаружения цикла в ориентированном графе, и если цикла нет, то вернуть тот же топологический порядок.

Пока я искал его, я столкнулся с различными методами, такими как поиск в глубину и топологическая сортировка, для обнаружения цикла в ориентированном графе.

Есть ли разница между этими двумя?


graph algorithm depth-first-search topological-sort
person Dhananjay Tyagi    schedule 15.10.2019    source источник
comment
У меня тоже была подобная путаница, но теперь я ясно: DFS: идите все глубже и глубже вместе с печатью. Топологическая сортировка: выберите каждую непосещенную вершину и сначала распечатайте ее зависимую вершину, прежде чем распечатать родителя (саму себя).   -  person Manish gour    schedule 31.05.2020

Ответы (4)


arrow_upward
7
arrow_downward

Итак, топологическая сортировка — это определенный порядок узлов ориентированного ациклического графа, который может быть достигнут поиском в глубину. Помимо поиска в глубину, существуют и другие методы поиска топологического порядка, такие как Алгоритм Кана.

person Konstantin Yovkov    schedule 15.10.2019
comment
Итак, топологическая сортировка — это всего лишь одно из применений DFS, верно? - person Dhananjay Tyagi; 15.10.2019
comment
@DhananjayTyagi Не только. Существует несколько подходов к топологической сортировке. Но да, вы можете применить DFS для достижения топологического упорядочения. - person plasmacel; 25.01.2020

arrow_upward
4
arrow_downward

Топологическая сортировка — это алгоритм на основе DFS на ориентированном ациклическом графе (DAG). Топологическое упорядочение — это линейное упорядочение вершин, такое что для каждого направленного ребра uv вершина u стоит перед v в упорядочении.

Топологическое упорядочение возможно тогда и только тогда, когда в графе нет направленных циклов. Но поиск в глубину можно выполнять как на ориентированных, так и на неориентированных графах.

person cong    schedule 25.11.2019

arrow_upward
1
arrow_downward

Топологическая сортировка использует DFS следующим образом:

  1. Звонок в ДФС
  2. Обратите внимание, когда все ребра были исследованы (т.е. время окончания)
  3. После завершения вершины вставьте идентификатор в начало топологической сортировки L.
  4. Завершенный список L является топологической сортировкой

Время выполнения: O(V+E)

По своей природе алгоритм топологической сортировки использует DFS в DAG. Свойства DFS имеют решающее значение для отображения возвращаемого списка в правильном топологическом порядке. Однако, как видно из ответов выше, упорядочение да невозможно без использования DFS. Примерами являются алгоритм Кана и параллельная сортировка.

person Colin Moody    schedule 03.12.2019
comment
что да заказывать? - person wilmol; 28.06.2020

arrow_upward
0
arrow_downward

Если вы хотите получить четкое представление, вы можете решить следующую задачу.

https:// onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&category=0&problem=1246&mosmsg=Отправка+получена+с+ID+25820106

Сначала вы можете перейти к простой DFS, но в некоторых случаях это не удается.

Например: DFS не работает в следующем тестовом примере:

5 4 (количество вершин и ребер соответственно)

(Описание краёв)

1 2

2 3

1 4

4 3

person mastan shaik    schedule 07.12.2020