[graph / DFS]: проблема с dfs в DAG - PullRequest
Новая
       32

[graph / DFS]: проблема с dfs в DAG

0 голосов
/ 10 сентября 2011

Вот псевдокод, скопированный из «вступления в алгоритм» для вашего удобства: 

DFS(G)
1  for each vertex u ∈ V [G]
2       do color[u] ← WHITE   //color changes from WHITE,GRAY,BLACK
3          π[u] ← NIL         //π[u] stands for the parent of vertex u
4  time ← 0
5  for each vertex u ∈ V [G]
6       do if color[u] = WHITE
7             then DFS-VISIT(u)

DFS-VISIT(u)
1  color[u] ← GRAY     ▹White vertex u has just been discovered.
2  time ← time +1
3  d[u] time           //d[u] is the time when u is entered
4  for each v ∈ Adj[u]  ▹Explore edge(u, v).
5       do if color[v] = WHITE
6             then π[v] ← u
7                         DFS-VISIT(v)
8  color[u] BLACK      ▹ Blacken u; it is finished.
9  f [u] ▹ time ← time +1   //f[u] is the time when u is exited

Вот мой вопрос: Предположим, что я получил DAG, его представление в списке приставок выглядит следующим образом: 

1:2, 4
2:5
3:1
4:
5:

Это должно выглядеть так: 

3 ---> 1 ---> 2 ---> 5
       |---> 4

тогда согласно псевдокоду π [1] должно быть равно NIL, и то же самое для π [3]. но, видимо, π [1] должно быть 3, верно? Я что-то упустил?

PS: причина, по которой я задаю вопрос, заключается в том, что я делал топологическую сортировку с использованием dfs. И моя мысль: 1. найти родителя каждой вершины, а именно π [u], 2. проверить каждую π [u], если π [u] == 0, то у вас 0 градусов и поместить вас в упорядоченный список.

1 Ответ

1 голос
/ 10 сентября 2011

Для вычисления топологической сортировки с использованием поиска по глубине ребра в группе DAG указывают в направлении зависимости (например, 1 зависит от 3 в вашем примере).

Таким образом, чтобы выполнить топологическую сортировку, вы быпредоставить DAG с ребрами, обратными из примера: 

1: 3
2: 1
3:
4: 1
5: 2

Используя этот график, вы создаете DFS, начиная с пустого списка для хранения топологической сортировки.После завершения DFS для вершины v, v добавляется в список.Этого можно достичь, добавив 

l ← []

после строки 4 DFS, где l хранит топологическую сортировку, и 

l.append(u)

после строки 8 из DFS-VISIT.

...