如何找到图中的所有前向和交叉边

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

正如你在这里看到的。