给定一个强连通的有向加权图。我需要从此图中找到一个强连接的子图，使得最大和最小权重边缘之间的差异为最小值。
更清楚地说，我需要删除边缘，这样删除边缘后，图形将仍然强连接并且 最大和最小权重边缘之间的差异为最小值。
这是一个示例:
第一行是该图的 N 个节点和 M 个边的数量。接下来的 M 条线代表该图的边缘。
3 6
1 2 8
2 3 32
3 1 16
1 3 81
3 2 243
2 1 27
所选的 N 节点子图将包含边:
1 2 8
2 3 32
3 1 16
最大和最小权重边之间的差异为:32 - 8 = 24。 这是所有选择中最小的一个。
我正在寻找最佳解决方案。最多有 3000 个节点和 5000 个边。
最佳答案
给定一个在 O(f(|V|, |E|)) 时间内测试给定有向图 G = (V, E) 是否强连通的算法，可以在 O(|E| 时间内解决这个问题*f(|V|, |E|)) - 如果在向已测试的有向图中添加或删除单条边后可以更快地完成强连通性测试，则效果会更好。
按权重升序对边进行排序，并按此顺序编号。最初，将第一条(权重最低)边添加到所选边的集合 E' 中；只要 E' 不是强连通的，就向其添加下一条边。如果该循环没有终止，则 G 不是强连通的。否则，当它停止时，在添加边 j 之后，我们已经找到了最小差异解假设我们包括边 1。将此 (1, j) 解记录为现任解。
现在从 E' 中删除边 1，以便边 2 成为 E' 中剩余的权重最低的边。将所有其他已决定的边保留在适当位置，并开始再次添加次低权重边，从边 j+1 开始，直到形成 SCG。对于每个 i <= |V|，可以重复此操作来计算最小差异解，假设所包含的最低权重边是边 i。保持最好的整体。
请注意，在求解起始点 i+1 时，不必删除为前一个起始点 i 确定的边:如果边 i, i+1, ..., j-1 这样做不形成 SCG，则边 i+1，i+2，...，j-1 也不形成 SCG。利用这一点意味着整个外循环仅运行 |E|次，而不是 O(|E|^2) 次。
关于algorithm - 找到强连通图，使得最大边和最小边之间的差异最小，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/68511351/