问题标签 [strongly-connected-graph]

给定一个强连通的有向加权图。我需要从这个图中找到一个强连接的子图，使得最大和最小权重边之间的差异最小。

更清楚地说，我需要以这样一种方式去除边缘，即在去除它们之后，图仍然是强连接的，并且最大和最小权重边缘之间的差异是minimum。

这是一个例子：

第一行是该图的 N 个节点和 M 条边的数量。接下来的 M 行代表该图的边缘。

选择的 N 节点子图将包含边：

最大和最小权重边缘之间的差异是：32 - 8 = 24。这是所有选择中最小的。

我正在寻找最佳解决方案。最多有3000个节点和5000 条边。

我正在阅读 Mark Weiss 的书（第 2 版），我无法理解这件事。这怎么可能。如果图是无向的，那么必须有一种方法可以访问每个人的每个节点。从图像（https://algorithms.tutorialhorizo​​n.com/check-if-given-undirected-graph-is-connected-or-not/）。如果我想访问 4 中的任何节点，我可以。唯一的方法是，我不能删除与 4 的连接。如果发生这种情况，这是一个图（在我看来，图需要有边）。图可以有“悬垂顶点”吗？

我正在尝试实现可以​​将散点图的所有连接部分作为二维向量数组返回的程序。

这是我写的代码：

输出是这样的：

请帮我弄清楚我做错了什么。输出应该是这样的。

我给的输入：

给定一个图 G 和 3 个顶点 a、b 和 c，在线性时间内验证从 a 开始并通过 b 的所有无限路径在到达 b 之前必然也从顶点 c 经过 如果只有顶点 c 在之前出现，则算法返回 True B 沿着从 a 开始到 b 的无限路径

我试图实现一个解决方案，但我不确定我以 3 种方式为图的节点着色黑色（n），白色（b），灰色（g）

Neo4j 相对较新，但我正在为以下问题寻找一些起始指针或代码示例：我有一个包含 3 种节点类型（人类、宠物和家庭）的 neo4j 图。我有两种关系类型：朋友和生活（见下图）。

我想可视化没有 Human-Pets 或 Home-Human 连接的 n 最大 Human-Human“集群”。所以只是人类朋友群的集群。知道我会怎么做吗？见下文，我想找到并可视化红色子图，因为它是最大的，但一般来说，前 n 会很棒：

1. G的拓扑类型是什么？
2. 有多少强连通分量？
3. 需要反转多少条边才能获得一个只有一个强连通分量的图？