我知道什么是正向和跨向。但是我发现很难在程序中实现它们以找到给定图中的所有前向和交叉边。
如有任何帮助，我们将不胜感激。
最佳答案
您可以使用 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
如你所见here .
关于c++ - 如何在图中找到所有前向和交叉边，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13053672/