单连通有向图

Question

根据CLRS第三版的定义，单连通有向图是对每对顶点(u，v)最多有1条唯一路径的有向图，现在我读到的大多数答案是，我们从图中的每个顶点运行DFS，如果在任何情况下我们找到一个交叉边或前向边，那么该图就不是单连通的。我可以理解前向边的概念，但是在这张图上运行这个algo

1->2<-3给出的结果是不是单连通的，而这个图是单连通的。我们有一个来自3 -> 2或1 -> 2的交叉边，这取决于哪个版本开始了整个过程(1或3)。如果我们从顶点2开始DFS，那么我们有两个交叉边1 -> 2和3 -> 2。

Answer 1

建议从每个节点运行DFS的答案意味着，一旦不能继续运行DFS (没有传出边缘)，就应该停止DFS，而不是从另一个节点开始。

在本例中，在您的示例中，您将从1开始(w.l.o)，发现2，就完成了。没有后缘

接下来，是一个全新的DFS，从3开始，发现2，并完成，同样没有后边。

这个想法基本上是通过定义来验证属性。您可以从每个节点u执行DFS，直到您发现每个v最多有一条从u到v的路径(DFS已经耗尽)，或者您在某个时候找到了从u到v的第二条路径，然后就完成了。