logo标签列表

单向连通有向图

javac++algorithmgraphclrs
3
根据CLRS第三版中的定义，单向连通图是指对于每一对顶点（u,v），u到v最多只有一条唯一的路径。现在我读过的大部分答案都说明我们需要从图中的每个顶点开始运行DFS算法，如果在任何情况下我们找到了一个交叉边或者一个前向边，那么这个图就不是单向连通的。我可以理解前向边的概念，但是在这个图上运行该算法会得出这样的结果：它不是单向连通的，而这个图实际上是单向连通的。我们有一个从3 -> 2 或者 1 -> 2的交叉边，具体取决于哪个顶点开始了整个过程（1还是3）。如果我们从顶点2开始DFS，则有两条交叉边：1 -> 2和3 -> 2。请问是否有人能够澄清一下？
你（或者他们）可能是把横叉边和反向边混淆了吧？因为反向边的存在（这里没有提到），明确表明一个图不是单连通的，而我同意你的观点，横叉边的存在并不一定表示如此。 - misberner
@misberner，考虑图1->2和从2->1的边。现在这个图也是单连通的。我们考虑对(1,2)这一对进行分析，从1->2只有一条路径，即单一的边。然后我们考虑对(2,1)这一对进行分析，从2->1只有一条唯一的路径，即边本身。尽管在从1开始的DFS中，我们发现了一条反向边，但这个图仍然是单连通的。 - Sachin Malhotra
这不是真的。回边意味着图中存在循环，因此在循环中的节点之间有无限多的非空路径：1 -> 2，1 -> 2 -> 1 -> 2等。 - misberner
@misberner 确实如此。很抱歉之前的评论没有考虑到这种情况。感谢您指出。 - Sachin Malhotra
1个回答
1

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

在这种情况下，在您的示例中，您将从1开始（w.l.o），发现2，然后完成。没有反向边
接下来，是一个全新的DFS，从3开始，发现2，再次完成，没有反向边。

基本思想是按定义验证属性。您从每个节点u开始进行DFS，直到发现对于每个v，从u到v最多只有一条路径（DFS用尽）或者您在某个时候找到了第二条从u到v的路径，然后您就完成了。

谢谢您澄清我的疑问。但我仍然不确定在图中只找到一条交叉边是否会导致它不是单连通的。您能解释一下这部分吗？ - Sachin Malhotra
@SachinMalhotra 这个想法是从节点 u 开始运行深度优先搜索，直到您找到以下情况之一：(1)到所有节点 v 的所有路径（如果每个像这样的 v 只有单条路径）。 (2) 一些节点 v 具有从 u 到 v 的两条路径 （反向边导致一个顶点，你已经访问了它，所以你找到了当前路径和第一次访问时发现的路径）。这些基本上是您的停止条件。这部分清楚吗？ - amit
是的，这部分很清楚。我理解了反向边的概念。那么交叉边呢？这个交叉边的概念每次都让我疑惑。在CLRS的问题回答中，我在网站上读到了以下内容:- 假设我们从顶点u开始对图G进行DFS。如果在以u为根的DFS树中存在前向或交叉边（v，w）（即v和w都是u的后代），则G有两条从u到w的路径：一条使用树边，另一条使用从u到v的树边，然后是前向或交叉边（v，w）。 - Sachin Malhotra
如果你从n开始进行深度优先搜索，并且找到了一条横叉边(u,v)，那么这意味着存在一条路径：(1)从n到u，(2)从n到v，(3)从u到v。但这也意味着存在一条路径n->...->u->v(1+3)，以及n->...->v(2)。边的类型并不重要，整个重点是当你进行DFS时，如果遇到一个已经发现了路径的节点，就会中止并返回false，对于每个节点都要单独进行DFS迭代。 - amit
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接