给定一个强连通的有向加权图。我需要从这个图中找到一个强连接的子图，使得最大和最小权重边之间的差异最小。
更清楚地说，我需要以这样一种方式去除边缘，即在去除它们之后，图仍然是强连接的，并且最大和最小权重边缘之间的差异是minimum。
这是一个例子：
第一行是该图的 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 条边。
给定一个算法来测试给定的有向图 G = (V, E) 是否在 O(f(|V|, |E|)) 时间内强连接，这个问题可以在 O(|E|*f( |V|, |E|))——如果在已经测试过的有向图上添加或删除一条边后可以更快地测试强连通性，那么效果会更好。
按重量递增的顺序对边进行排序，并按此顺序编号。最初，将第一个（最低权重）边添加到选定边的集合 E'；只要 E' 不是强连接的，就向它添加下一条边。如果这个循环没有终止，那么 G 不是强连接的。否则，当它停止时，在添加边 j 之后，我们已经找到了一个最小差解，因为我们包含边 1。将此 (1, j) 解决方案记录为现任者。
现在从 E' 中删除边 1，以便边 2 是 E' 中剩余的最低权重边。将所有其他已确定的边保留在原位，并从边 j+1 开始再次开始添加下一个最低权重的边，直到形成 SCG。假设包含的最低权重边是边 i，对于每个 i <= |V|，可以重复此操作以计算最小差解。保持整体最佳。
请注意，在求解起点 i+1 时，不必去掉为前一个起点 i 确定的边：如果边 i、i+1、...、j-1 不形成SCG，然后边 i+1, i+2, ..., j-1 也不形成 SCG。利用这意味着整个外部循环只运行 |E| 次，而不是 O(|E|^2) 次。