问题标签 [strongly-connected-graph]

我需要检查有向图是否是强连接的，或者换句话说，是否所有节点都可以被任何其他节点（不一定通过直接边）到达。

一种方法是在每个节点上运行 DFS 和 BFS，并查看所有其他节点仍然可以访问。

有没有更好的方法来做到这一点？

要检查一个顶点 v 是否是一个特殊的顶点，是否足以表明它在一个 sink 强连通分量中？难道我们不需要证明底层的无向图是连通的吗？如果是这种情况，检查顶点是否特殊的最佳方法是什么

我正在尝试自学图论，现在尝试了解如何在图中找到SCC。我已经阅读了关于 SO 的几个不同的问题/答案（例如，1、2、3、4、5、6、7、8），但我找不到一个可以遵循的完整分步示例。

根据CORMEN (Introduction to Algorithms)，一种方法是：

1. 调用 DFS(G) 计算每个顶点 u 的完成时间 f[u]
2. 计算转置(G)
3. 调用 DFS(Transpose(G))，但在 DFS 的主循环中，按 f[u] 递减的顺序考虑顶点（如步骤 1 中计算的）
4. 将步骤 3 的深度优先森林中每棵树的顶点输出为单独的强连通分量

观察下图（问题是来自这里的 3.4。我在这里和这里找到了几个解决方案，但我试图自己分解并理解它。）

第 1 步：调用 DFS(G) 计算每个顶点 u 的完成时间 f[u]

从顶点 A 开始运行 DFS：

请注意格式为 [Pre-Vist, Post-Visit] 的 RED 文本

第 2 步：计算转置 (G)

步骤 3. 调用 DFS(Transpose(G))，但在 DFS 的主循环中，按 f[u] 递减的顺序考虑顶点（如步骤 1 中计算的）

好的，所以顶点按访问后（完成时间）值递减的顺序排列：

{E、B、A、H、G、I、C、D、F、J}

所以在这一步，我们在 G^T 上运行 DFS，但从上面列表中的每个顶点开始：

• DFS(E)：{E}
• DFS(B)：{B}
• DFS(A)：{A}
• DFS(H): {H, I, G}
• DFS(G)：从列表中删除，因为它已经被访问过
• DFS(I)：从列表中删除，因为它已经被访问过
• DFS(C): {C, J, F, D}
• DFS(J)：从列表中删除，因为它已经被访问过
• DFS(F)：从列表中删除，因为它已经被访问过
• DFS(D)：从列表中删除，因为它已经被访问过

步骤4：将步骤3的深度优先森林中每棵树的顶点输出为单独的强连通分量。

所以我们有五个强连通分量：{E}, {B}, {A}, {H, I, G}, {C, J, F, D}

这是我认为是正确的。但是，我在这里和这里找到的解决方案说 SCC 是 {C,J,F,H,I,G,D} 和 {A,E,B}。我的错误在哪里？

我遇到了一个类似这样的问题。

我们得到一个无向图，其中每条边都有一个值。现在额外的限制是不能从较高价值的边缘移动到较低价值的边缘。一个人总是必须从较低的价值转向较高的价值。

从图形上看，问题可以描述为

所以在这里我们可以从 7 -> 1 -> 3 -> 4 移动，但不能从 4 -> 3 -> 1 移动。所以在这个图中，我们被要求在这里找出像 (1, 3, 7) 这样的强连通分量.

我曾尝试将 Kosaraju 算法与这样的约束一起使用。

但我认为逻辑是错误的，我无法找出它失败的地方。有人可以指出错误并显示某种伪代码吗？

谢谢你。

我正在使用networkx（第一次）来检查图形是强连接还是nt，但我发现它没有定义。如文件所述，它应该可以工作。？？

我的跑步：

Traceback（最近一次调用最后一次）：文件“”，第 1 行，在

NameError：名称“is_strongly_connected”未定义

谢谢

我正在 MATLAB 中编写图像处理程序的原型，并希望在原型阶段完成后将其移植到 javascript。

我对 javascript 不是很熟悉，但似乎有很多可用的图像处理库，所以我猜我在 MATLAB 中使用的大多数基本图像处理函数已经在某个地方实现了。然而，我在 MATLAB 中使用的一个更强大的函数称为“regionprops”，它基本上计算出二进制图像的强连通分量，并输出与每个“分量”相关的一堆统计数据，例如面积、边界盒子，重心等

在 js 中提供此功能的最短方法是什么（即我的实现最少）？作为最后的手段，我会将图像转换为图形以使用强连接组件库，如果我可以避免这种情况（以及随后与图像相关的计算），我想知道。

非常感谢指向文档和库的指针！谢谢，特普。

在 Kosaraju 的算法中，完成时间是从反向图生成的。然后，通过执行 DFS 从原始图中发现强连通分量，从较早生成的最大完成时间开始到最低完成时间。

Kosaraju 算法的完成时间可以从原始图生成吗？那么，是否可以通过DFS从最短完成时间到最长完成时间发现强连通分量呢？

在我看来，情况就是这样，但这只是我的预感。

问题：将问题 1 中图的一组顶点划分为强连通分量（SCC）。即，指定哪些顶点在第一个强连通分量中，哪些在第二个中，依此类推。

有没有人能够确认我正确地做到了这一点？也就是说，当我到达顶点 4 时，我可以选择将第一个 SCC 设为 1、7、2、4、3（如图所示）或 1、7、2、4、6、5，具体取决于我选择的旅行方式。有没有办法解决这个问题，还是我可以简单地选择？

命令：

1,2,7,3,4,5,8,6

SCC：

1,7,2,4,3

5

8

6

我已经使用neo4j-mazerunner来分析我图表上的strong_connected_components关系。该过程已经结束，现在我在节点上获得了strong_connected_components属性。

我使用以下查询来获取不同节点的节点行：

我不确定如何对图形进行密码查询以可视化生成的集群。

任何帮助都会得到帮助。

我正在尝试实现 Tarjan 的强连接图算法（https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm），这是我的代码，我很困惑为什么顶点4和顶点5也作为强连接组件输出？

我正在使用一个非常简单的图表，只有 5 个节点要测试。我的代码是用 Python 2.7 编写的。