问题标签 [strongly-connected-graph]

我正在使用 Google Guava Graph API 实现 Kosaraju 的算法，但目前坚持MutableValueGraph使用标准 guava API 获得转置。

下面是我的代码：

有人可以建议一种将图形转换为其转置保持底层接口相同（MutableValueGraph）的好方法吗？有没有办法做到这一点？如果没有，我很乐意更改底层接口。

我正在尝试编写一个算法来确定一个图是否是强连接的。我认为我的代码几乎是正确的，尽管我不断收到 StackOverFlowError。我个人认为，因为我正在测试我的算法的图表中有一个循环，所以我的代码不理解它并进入一个循环。但是我正在使用一个数组来查看一个节点是否已经被访问过！所以这不应该发生！请帮助我了解我的代码有什么问题。无论如何，这是我的代码：

这就是我从 main 调用我的 DFS 函数的方式：

我想使用 R 提取图的巨大组件的邻接矩阵。

例如，我可以创建 Erdos-Renyi g(n,p)

在这里，我只想提取那些红色节点的邻接矩阵。

在此处输入图像描述

来自https://algs4.cs.princeton.edu/42digraph/

43. 有向图中的可达顶点。设计一个线性时间算法来确定一个有向图是否有一个可以从其他每个顶点到达的顶点。

Kosaraju-Sharir 算法为我们提供了强连通分量。Java 代码可以在这里看到。将每个 SCC 减少到一个顶点，一个外度为零的顶点可以相互到达。

问题是，似乎每个人都在谈论减少 SCC 而没有提供细节。这样做的有效算法是什么？

用 随机生成的图networkx。我想从此图中检索强连接的组件。

为什么我使用内置networkx函数只能得到一个大 scc？

即使边缘的力密度为 0.1，我也得到相同的 SCC。

In Kosaraju algorithm I came across two possible implementations:

1) Search for strongly connected components in the reversed graph in the topological order of vertices in the original graph.

2) Search for strongly connected components in the original graph in the topological order of vertices in the reversed graph.

I wanted to that is it wrong to search for strongly connected components in the original graph using vertices in its reversed topological order. This will be better in terms of memory also as there is no need for a new adjacency list.

sources :1) E-Maxx , 2) CLRS book

我想在强连接组件中找到从节点到其他节点的最短路径，节点可以任意选择。两种搜索方法浮现在脑海中的深度优先搜索或广度优先搜索。
可以证明在某些情况下一种比另一种更可取吗？
一种情况可能是稀疏图与密集图 SCC。

我试图解决一个问题来设计一种算法来确定直接图是否是半连通的。有人说可以通过对图中的每个 SCC 使用拓扑排序来完成。并且 SCC 保证是 DAG。但是，我认为 SCC 图一定是一个圆，为什么它是一个 DAG，因为 DAG 表示没有圆。

我有这个结构的图表：

这个图其实很大，有 6378 个节点和 39932 条边。我的问题是图表已断开连接，我希望图表完全连接且没有断开连接的组件。

有人可以帮我写python代码吗？从星期天开始我就一直在摇头。谢谢

我写了这段代码，但它运行没有错误。尽管如此，它仍然无法完成工作。我知道我做的不对

编辑：所以我以这种方式重写了代码，现在它需要永远执行。我选择了一个起始顶点作为键，并且这个键的值中的每个其他节点节点，我都尝试添加到该值中。也许我做错了什么；有人请帮助我！

强连通有向图是一个有向图，其中对于每两个顶点 和 ，都有一条从 到 的有向路径和一条从 到 的直接路径。令 = (, ) 为强连通有向图，令 = (, ) ∈ 为图中的一条边。设计一个有效的算法来判断 ' = (, ∖ {})，没有边的图是强连通的。解释其正确性并分析其运行时间。

所以我所做的是运行 BFS 并对标签求和，一次在原始图上，然后在没有边缘的 G' 中再次（再次从 ），然后：如果第二个总和（在 G' 中）< 原始总和（在 G 中）然后该图没有强连接。

PS 这是我考试中的一个问题，我只得到了 3/13 分，我想知道我是否应该上诉..