c++ - グラフ内のすべての前方エッジと交差エッジを見つける方法

Question

フォワードとクロスエッジが何であるかを知っています。しかし、特定のグラフですべての前方エッジと交差エッジを見つけるために、それらをプログラムに実装するのが難しいと感じています。

この点で何か助けていただければ幸いです。

Answer 1

DFS 横断を使用して、すべてのグラフ エッジを分類できます。

DFS-Visit(u)         ▷ with edge classification. G must be a directed graph

1.        color[u] ← GRAY
2.        time ← time + 1
3.        d[u] ← time
4.        for each vertex v adjacent to u
5.            do if color[v] ← BLACK
6.                then if d[u] < d[v]
7.                            then Classify (u, v) as a forward edge
8.                            else Classify (u, v) as a cross edge
9.                        if color[v] ← GRAY
10.                            then Classify (u, v) as a back edge
11.                       if color[v] ← WHITE
12.                            then π[v] ← u
13.                                 Classify (u, v) as a tree edge
14.                                 DFS-Visit(v)
15.        color[u] ← BLACK
16.        time ← time + 1
17.        f[u] ← time

ここでわかるように。