问题标签 [strongly-connected-graph]

问问题

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

46 问题
Newest
Active
Bountied
318
Unanswered
0 投票
0 回答
150 浏览

algorithm - 添加边时更新强连通分量

令 G = (V, E) 为强连通有向图。从图 G' = (V, {}) 开始。我们得到一个 E 中的边列表 L，这样我们添加到 G' 的 L 中的每条边（按顺序）连接两个强连通分量。当我们一次添加一条边时，跟踪 G' 的强连通分量的快速算法是什么？在每一步使用 Kosaraju 或 Tarjan 算法需要 O(|E|(|V|+|E|)) 时间，我猜这可以改进。

0 投票
1 回答
245 浏览

networkx - 删除节点（但保持图强连接）

我正在尝试模拟一个带有一些直线障碍物的矩形房间，因此我将问题表述为 networkx 中的图形。要添加障碍物，我将选择节点，然后删除其所有边。为了防止图形分区，这是我使用的代码

但似乎 'nx.number_connected_components(copy) '引发错误：'function' 对象没有属性 'is_directed'

这对我来说毫无意义，因为该图是一个 grid_2d_graph，它显然是无向的。有什么问题，我该如何解决？

0 投票
1 回答
105 浏览

prolog - Anytime strongly connected components via Prolog

Markus Triska has reported an algorithm to determine strongly connected components (SCC). Is there a solution which determines the SCC without making use of attributed variable and that can work anytime. So that some vertices can have infinitely many edges?

I am asking because I am wondering whether B-Prologs anytime tabling which they call eager can be replicated. B-Prolog determines clusters which is their name for SCC. But it has also a tabling mode where it returns tabled results eagerly.

user502187
0 投票
1 回答
411 浏览

graph-visualization - 是否可以在 Gephi 中可视化有向图的强连通分量？

我想在 Gephi 中可视化有向图的强连通分量。我可以得到否。图中的 SCC，但找不到将其可视化的方法。我使用“Force Atlas 2”来布局近 6000 个节点（~20000 条边）的图形，但我从可视化图形中得到的只是节点的“出度”边。有人可以帮助我如何在 gephi 或其他方式中可视化强连接的组件。非常感谢！

0 投票
1 回答
220 浏览

boost - 使用 listS 提升强组件

在 listS 而不是 vecS 上做强连通分量的图的例子并不多。这是 vecS 的等效示例

但是当我从 vecS 更改为 listS 时，它会中断。我知道问题是由于顶点索引和输出向量索引中的某种类型的不匹配，但我无法完全想出解决它的方法。最接近的答案是哪些 VertexList 类型对 depth_first_search 有效，但这适用于 DFS，不能外推到 SCC。

0 投票
1 回答
570 浏览

graph - 找到一条从顶点 s 到顶点 t 的路径，其中颜色交替最少

设$G=(V,E)$为有向图，设$c:E\mapsto {红、蓝}$为红色和蓝色的边缘着色。让 s,t 是 G 中的顶点。找到一条从 s 到 t 的路径（如果存在），使得沿着这条路径的颜色变化次数最少。

我试图做如下：

  1. 让$G_r$是通过去除 G 的所有蓝色边缘$G_b$得到的图。让 是通过去除 G 的所有红色边缘得到的图。
  2. 让$G_{r}^{SCC}$ 是 的强连通图$G_r$，使用该算法计算。
  3. 让$G_{b}^{SCC}$是 的 强连通图$G_b$，使用 该算法计算。
  4. 将 的顶点 $G_{r}^{SCC}$着色为红色，将 的顶点着色为 $G_{b}^{SCC}$蓝色。
  5. 设为与 $G'=(V',E')$合并得到的图。$G_{r}^{SCC}$$G_{b}^{SCC}$
  6. 将 G' 中每个（现有）边的权重定义为 0。
  7. 对于每个$(u,v)\in E$这样的 u 属于强连通分量$C_u$，v 属于强连通分量$C_v$，请执行以下操作：
  • 如果$C_u \neq C_v$并将$color(C_u)\neq 颜色(C_v)$边缘添加$(C_u ,C_v)$到 G' 并将其权重定义为 1。
  1. 使用 Dijkstra 算法找到从 s 的蓝色强连通分量到 t 的蓝色和红色强连通分量的最短路径。
  2. 使用 Dijkstra 算法找到从 s 的红色强连通分量到 t 的蓝色和红色强连通分量的最短路径。
  3. 让 p 表示我们刚刚找到的四个路径中的最短路径。（即，p 具有最少数量的颜色替代）。p 是一系列强连通分量。使用 DFS 展开它们中的每一个，以在 G 中找到相应的路径。

该算法可以在 O(E+V*log(v)) 中运行。可以改进或简化吗？

0 投票
1 回答
195 浏览

java - Tarjan的算法实现，低价值节点问题

我正在尝试对图中的一组节点执行 tarjans 算法，我可以成功找到强连接组件，但是根节点或低值节点始终处于关闭状态，即使对于只有 1 个元素的 SCC，根节点也不匹配元素 例如：

其中顶部是低值节点，底部是构成 SCC 的 1 元素

我目前拥有的代码在这里

我怀疑问题在于设置低值。我认为不需要任何其他类信息，因为从图中检索边没有问题

0 投票
1 回答
49 浏览

algorithm - 强连通分量

如果您不知道 SCC 算法的工作原理，请阅读这篇文章：https ://www.hackerearth.com/practice/algorithms/graphs/strongly-connected-components/tutorial/ （这是我能找到的最好的文章）。

在找到每个节点的完成时间后，我们反转原始图并从最高时间节点开始运行 DFS。如果我们从原始图中的最小节点开始运行 DFS 会怎样？为什么它不起作用？

0 投票
1 回答
35 浏览

python - 具有 n 到 m 关系的 Python Cluster 连接元素

这不是家庭作业（请参阅我的个人资料）。我没有计算机科学背景，这个问题出现在一个应用机器学习问题中。我很确定我不是第一个遇到这个问题的人，因此我正在寻找一个优雅的解决方案。与原始实现相比，我更喜欢使用 python 库的解决方案。

假设我们有一个连接字母和数字的字典作为输入

每个字母可以连接到多个数字。一个数字可以连接多个字母。但是每个字母只能与一个数字连接一次。

如果我们查看字典，我们会意识到，数字3与字母'A'和字母相连，'B'因此我们可以将'A'和'B'放入一个簇中。该字母的数字'C'不存在于其他字母中。因此，我们不能'C'进一步对字母进行聚类。预期的输出应该是

我认为这应该与图算法和连接子图有关，但我不知道从哪里开始。

0 投票
1 回答
70 浏览

java - 强连通分量

我遇到了问题，我的输出不正确

我的输入：

我的输出：

输出应该是这样的：

我什至不知道为什么会有这样的错误。我将代码从 https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/更改为我的代码，并增加了输入的机会。我问过这个问题，一位朋友说“这是添加 w 后 addEdge 方法中两个代码的输出，在你的代码中 w 被添加到所有元素中，而在原始中只添加到图 v”但我不知道如何去做吧


12345678910