单连通有向图

Question

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

1-->2<--3将给出一个结果：它不是单连通的，而这个图是单连通的。我们有一个从3->2或1->2的交叉边，这取决于从哪个vertext开始整个过程（1或3）。如果我们从顶点2开始DFS，那么我们有2条交叉边1->2和3->2。谁能澄清一下吗？

Answer 1

建议从每个节点运行DFS的答案意味着，一旦无法继续（没有留下输出边），就应该停止DFS，而不是从不同的节点开始。

在这种情况下，在您的示例中，您将从1开始(w.l.o)，发现2，您就完成了。No back edgees
下一个，是一个全新的DFS，从3开始，发现2，并且完成，再次没有back edge。

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