我正在做一项任务，其中一个问题要求派生一种算法来检查有向图 G=(V,E) 是否是单连接的（对于所有不同的顶点 u，从 u 到 v 最多有一个简单的路径， v 的 v。
当然你可以蛮力检查它，这是我现在正在做的，但我想知道是否有更有效的方法。谁能指出我正确的方向？
问问题
15372 次
7 回答
5
这个问题有更好的答案。你可以在 O(|V|^2) 中做到这一点。并且通过更多的努力，您可以在线性时间内完成。
首先你找到G的强连通分量。在每个强分量中，你搜索找到这种情况：1）如果这个分量中有一个前边，它不是单连通的，2）如果这个分量中有一个交叉边，它不是单连接的，3）如果在以顶点 u 为根的树中至少有两个后边到 u 的正确祖先，那么它不是单连接的。
这可以在 O(E) 中完成。（我认为除了案例3。我不能很好地实现它！！）。
如果上述情况均未发生，则应检查 G^SCC 上是否存在交叉边或前边（图 G，将强组件替换为单个节点），因为我们没有后边，可以通过在 O(|V|^2) 中在该图的每个顶点上重复 dfs。
于 2010-06-05T05:53:21.170 回答
4
你试过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 没有重复。
于 2010-03-24T21:01:00.670 回答
3
读这个。它真的很好解释。
于 2014-01-05T08:02:51.097 回答
0
我不同意它的复杂性将是 O(V^2)，因为在 DFS 中，我们不会像在算法简介中看到的那样为每个顶点调用它，语法是 DFS(G)。我们只对整个图调用 DFS，而不像 BFS 那样对任何单个顶点调用。所以在这种情况下，根据我的说法，我们必须通过调用 DFS 一次来检查它。如果再次遇到访问的顶点，则图不是单连接的（当然我们必须为每个断开连接的组件调用它，但它已经包含在代码中）。所以复杂度将是 O(V+E)。因为这里 E=V，所以复杂度应该是 O(V)。
于 2013-06-30T13:11:21.750 回答
0
我想到了这个：1）从任何顶点运行DFS，如果所有顶点都被DFS覆盖而没有前向边（不能有交叉，否则不会覆盖所有顶点），那么它可能是一个潜在的候选者。
2）如果在 DFS 中找到的顶点（级别 j）具有到级别 i 的后边缘，那么在它之后没有找到其他顶点应该具有朝向级别小于 j 的任何顶点的后边缘，并且每个顶点都可以到达根（用第二个 DFS 检查）。
如果这是正确的，这会在线性时间内完成。
于 2013-11-09T20:36:33.593 回答
0
看一下简单路径的定义。循环图可以是单连接的。DFS不适用于A->B, B->A，它是单连接的。
下面的论文使用强连通分量来解决这个问题。
于 2017-11-02T02:24:36.630 回答
-1
从每个顶点运行一次 DFS。当且仅当没有前向边并且组件内没有交叉边时，该图是单连接的。
复杂度：O(VE)
于 2011-05-18T23:48:28.080 回答