问题标签 [strongly-connected-graph]

我正在实现 Kosaraju 的两遍算法，该算法可以计算有向图中的强连通分量。

我可以用小输入数据得到正确的结果，但是当输入数据较大时

( 70M txt ,警告！！这个文本文件有将近70M的大小，用这个url的下载软件下载这个大文件。如果你没有下载软件，你可以复制这个url到你的浏览器中http://pan.baidu.com/s/1i5Hmf5N 下载它），

大约 1 小时后，它显示“pythonw.exe 已停止工作”。Python 应该运行以获得正确的答案。

我该如何解决？是不是内存有问题？请帮我一个忙。

这是大数据结果：

我的代码在这里：

这是小测试文件：

这是小测试文件的正确部分结果：

考虑一个断开有向图的示例， 其中G={V,E}顶点V={a,b,c,d}和边是孤立的。E={(a->b),(a->c)}d

根据这里的答案：（对强连通图的最小补充），确保该图所需的最小边数为 3。

如何找到将这些边添加到哪里，即该图中边的起始和结束顶点？

边以 Xij 的形式给出，表示在第 i 个和第 j 个顶点之间是否有边。我正在解决整数优化问题，并想将这个约束添加到它。

我正在尝试实现 tarjan 的算法进行练习。我决定生成一个随机图作为算法的输入，一次添加一条边。

我生成了随机图并保存在一个文件中，如下图

我在 test.edgelist 文件中得到的输出是这样的。

但是，在我实现的 tarjan 算法中，输入格式为

我希望在循环中使用随机生成的图作为输入。

我怎么没有得到 {}？另外，如果有更好的方法来实现这一点，请帮忙，因为对于海量数据集，很难将其保存为单个列表（add_edge() 将边缘添加到列表中）

我正在尝试编写一个算法，它给出一个图 G 和 2 个节点“x”和“y”作为输入，它返回是否存在从“x”到“y”的循环路径

首先找到强连通分量然后检查 x 和 y 是否属于同一个强连通分量是一个好主意。
如果它们属于不同的连通分量，比如 x 属于 C1，y 属于 C2，那么如果存在从 C1 到 C2 的路径，那么我们可以说存在从 x 到 y 的循环路径。

对于一个图，在找到强连通分量之后，如何找到彼此有路径的 SCC 的数量？我想查找是否有从 SCC1 到 SCC2 的路径。

我有一个有向图的 SCC。我想找到一条从顶点 s 开始至少访问此 SCC 中每个顶点一次的路径。我知道这可能是一个 NP 问题。无论如何，我该如何解决这个问题？

“给定节点数和连接这些节点的边数，排列这些边，使最大数量的节点强连接。返回可以强连接的节点数。”

我想知道是否有这个公式？如果没有，我该如何解决这个问题？任何帮助，将不胜感激！

对于具有n 个节点的有向图G(V, E)，我想创建一个整数数组a，其长度为n。如果存在从节点 1 到 2 的路径，则，如果它们在同一个强连通分量中，如果没有从节点 2 到 3 的路径，则有。a[1] <= a[2]a[1] = a[2]a[2] > a[3]

我觉得时间复杂度应该是O(n + m)，因为求强连通分量的时间复杂度就是它。但我不知道如何为它输出一个数组，有人可以帮忙吗？谢谢。

有一个图和它所有的强连接组件，我想知道找到连接两个 SCC 的弧的最有效方法是什么。我找到的所有解决方案都涉及遍历所有节点，我想知道是否有办法在不这样做的情况下做到这一点，特别是在我用来在图中找到 SCC 的 Tarjan 算法期间。无论如何以线性方式进行？

非常感谢！