logo标签列表

有向图连通性

algorithmgraph
4
给定一个有向图 G，如何找到一个顶点 v，使得从 v 到 G 中的每个其他顶点都有一条路径？这个算法应该在线性时间内运行。是否存在解决此问题的现有算法？如果不存在，请提供一些见解，以便在线性时间内解决该问题（我只能想到肯定不需要线性时间的解决方案）。
2
查看Skienna的“算法设计手册”。其中有一章关于图。 - duffymo
3个回答
3

创建一个名为 L 的顶点列表。

选择其中一个顶点，称其为V。从 V 开始遍历图形，在此过程中从列表中移除点，并保留一个未访问的边缘堆栈。当您找到一个循环（您访问的某个顶点不在列表上）时，从堆栈中弹出一条边并继续。

如果堆栈为空且 L 不为空，则从 L 中选择一个新顶点，将其称为 V，并像之前一样继续。

当 L 最终为空时，您最后选择的 V 就是答案。

1
即使在图中没有实际满足条件的节点，这也会返回一些节点。我不知道这是否对 OP 有影响，但我认为应该提到。 - svick
2
是的，没错。我认为你可以尝试从它开始遍历图来检查答案是否足够（如果你第一次没有猜对的话），并在遍历过程中标记所有顶点。我相信这仍然是线性的。如果测试失败，则没有解决方案。 - Mike Sokolov
2

这可以在边的数量上以线性时间完成。

  1. 找到强连通分量。
  2. 将每个组件压缩为单个节点。
  3. 在压缩后的图上进行拓扑排序，最高排名的节点将有一条到其他所有节点的路径（如果图形连接在一起的话）。
0

我认为我得到了正确的答案。

  1. 获取SCC。
  2. 将每个组件压缩成单个节点。
  3. 检查每对相邻节点是否可达。

这是充分必要条件。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接