确定有向图是否单连通的最有效方法是什么？
https://stackoverflow.com/questions/2511295
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我正在做一项作业，其中一个问题要求导出一种算法来检查有向图 G=(V,E) 是否单连通（对于所有不同的顶点 u 至多有一条从 u 到 v 的简单路径， v 的 v。
当然你可以暴力检查它，这就是我现在正在做的，但我想知道是否有更有效的方法。有人能指出我正确的方向吗？
解决方案
您是否尝试过 DFS 。
Run DFS for every vertex in the graph as source
If a visited vertex is encountered again, the graph is not singly connected
repeat for every unvisited vertex.
The graph is singly connected.
复杂度为O（V ^ 2），O（v）的DFS作为不重复。
其他提示
有对这个问题的一个更好的答案。你可以这样做，在O（| V | ^ 2）。并与更多的努力，你能做到这一点的线性时间。
首先找到在每个强部件G.强烈连接组件，则搜索找到此情况下： 1）如果在该组件的前边缘，它不是单独连接， 2）如果在该部件的横边，它不单独连接， 3）如果在树的至少两个后缘在顶点u扎根，到u的适当的祖先，那么它不单独连接。
这可以在O（E）来进行。 （我认为除了壳体3我无法实现它很好!!）。
如果没有上述发生的情况下，应检查是否有一个横边缘或G ^ SCC前边缘（图G中，与单节点代替强部件），因为我们没有backedges，它能通过重复上DFS在O此图的每个顶点进行（| V | ^ 2）。
读 这个. 。确实解释得很好。
我不同意，它的复杂性会为O（V ^ 2），如DFS，我们不也把它用于介绍每个顶点的看向算法书，语法是DFS（G）。我们只能打电话DFS是全图形不是不像BFS任何一个顶点。因此，在这种情况下，这里根据我我们通过调用DFS once.If拜访顶点再次遇到，曲线图中没有单独连接到检查（明确，我们必须把它的每一个组成部分断开，但它已经包含在代码）。所以复杂性将是O（V + E）。如这里Ë= V因此复杂性应该是O（V）。
我认为这样的： 1）运行DFS从任何顶点，如果所有的顶点都覆盖在DFS没有向前边缘（不可能有横作为别的不是所有的顶点将被覆盖），则它可以是一个潜在的候选者。
这是在DFS发现2）如果一个顶点（水平j）具有后边缘，以电平，那么我没有其他顶点后发现它应具有朝向与水平的任何顶点后边缘小于j和每个顶点多是可达到根（与第二DFS选中）。
此做它在线性时间，如果这是正确的。
看一看简单的路径的定义。的循环图形可以单独连接。 DFS不会为了A->B, B->A，其被单独地连接的工作。
下面的纸张用途强连通分量来解决这个问题。
运行DFS从每个顶点一次。该图表单独连接的，如果与 只是如果没有前边缘和有内无交叉边缘 成分
复杂度：O（V.E）
