确定有向图是否单连通的最有效方法是什么？
我正在做一项作业，其中一个问题要求导出一种算法来检查有向图 G=(V,E) 是否是单连通的（对于所有不同的顶点 u，从 u 到 v 至多有一条简单路径， v of V.
当然你可以暴力检查它，这就是我现在正在做的，但我想知道是否有更有效的方法，有人能指出我正确的方向吗？
I am working on an assignment where one of the problems asks to derive an algorithm to check if a directed graph G=(V,E) is singly connected (there is at most one simple path from u to v for all distinct vertices u,v of V.
Of course you can brute force check it, which is what I'm doing right now, but I want to know if there's a more efficient way. Could anyone point me in the right direction?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
对于这个问题有一个更好的答案。你可以在 O(|V|^2) 内做到这一点。只要付出更多努力，您就可以在线性时间内完成。
首先你找到G的强连通分量。在每个强分量中，你搜索找到这种情况：
1）如果该组件中存在前向边缘，则它不是单连接的，
2）如果该组件中有交叉边，则它不是单连接的，
3) 如果树中至少有两个以顶点 u 为根的后边到 u 的真祖先，则它不是单连接的。
这可以在 O(E) 内完成。 （我认为除了情况3。我无法很好地实现它！！）。
如果上述情况都没有发生，你应该检查G^SCC上是否有交叉边或前向边（图G，用单个节点替换强组件），因为我们没有后边，可以通过以下方式完成在 O(|V|^2) 内对该图的每个顶点重复 dfs。
There is a better answer for this question. you can do that in O(|V|^2). and with more effort you can do it in linear time.
First you find strongly connected components of G. in each strong component, you search to find this cases:
1) if there is a forward edge in this component, it is not singly connected,
2) if there is a cross edge in this component, it is not singly connected,
3) if there are at least two back edges in tree rooted at vertex u, to proper ancestors of u, then it is not singly connected.
this can be done in O(E). ( I think except for case 3. I couldn't implement it well!! ).
If none of cases above occurred, you should check whether there is a cross edge or a forward edge on G^SCC ( graph G, with strong components replaced with single nodes), since we don't have backedges, it can be done by repeating dfs on each vertex of this graph in O(|V|^2).
您是否尝试过DFS。
复杂度 O(v^2), o(v) dfs 不重复。
Have you tried DFS.
Complexity O(v^2), o(v) dfs as no repetition.
我不同意它的复杂度是 O(V^2)，因为在 DFS 中，我们不会为每个顶点调用它，正如算法简介一书中所见，语法是 DFS(G)。与 BFS 不同，我们只针对整个图调用 DFS，而不是针对任何单个顶点。因此，在这种情况下，根据我的说法，我们必须通过调用 DFS 一次来检查它。如果再次遇到访问过的顶点，则该图不是单连接的（当然我们必须为每个断开连接的组件调用它，但它已经包含在代码中）。所以复杂度为 O(V+E)。由于这里 E=V，因此复杂度应该是 O(V)。
I don't agree that its complexity will be O(V^2), as In DFS we don't call it for every vertex as see in Introduction to algorithm book also, syntax is DFS(G). We only call DFS for whole graph not for any single vertex unlike BFS. So here in this case according to me we have to check it by calling DFS once.If a visited vertex is encountered again, the graph is not singly connected(definitely we have to call it for every disconnected component but it already included in the code). SO the complexity will be O(V+E). As here E=V therefore complexity should be O(V).
我想到了这一点：
1）从任意顶点运行DFS，如果所有顶点都被DFS覆盖并且没有前向边（不能有交叉，否则不会覆盖所有顶点），那么它可以是潜在的候选者。
2）如果在DFS中找到的一个顶点（级别j）具有到级别i的后边缘，则在它之后找不到其他顶点应该具有朝向级别小于j的任何顶点的后边缘，并且每个顶点都可以到达级别i root（用第二个 DFS 检查）。
如果正确的话，这会在线性时间内完成。
I thought of this :
1) Run DFS from any vertex, if all vertices are covered in the DFS with no forward edges(there can be no cross as else not all vertices will be covered), then it can be a potential candidate.
2) If a vertex(level j) which is found in the DFS has a back edge to level i then no other vertex found after it should have a back edge toward any vertex with level less than j and every vertex much be reachable to the root(checked with second DFS).
This does it in linear time if this is correct.
看一下简单路径的定义。有环图可以是单连通的。
DFS不适用于单连接的A->B、B->A。下面的论文使用强连通分量来解决这个问题。
https://www.cs.umd.edu/~samir/grant/ khuller99.ps
Take a look at the definition of simple path. A cyclic graph can be singly connected.
DFSwon't work forA->B, B->A, which is singly connected.The following paper uses strongly connected component to solve this.
https://www.cs.umd.edu/~samir/grant/khuller99.ps
从每个顶点运行一次 DFS。该图是单连通的，如果并且
仅当a内没有前向边缘且没有交叉边缘时
成分。
复杂度：O(VE)
Run DFS once from each vertex. The graph is singly connected if and
only if there are no forward edges and there are no cross edges within a
component.
Complexity : O(V.E)