if (X == Y)
return 0 // We don't need any edges.
if (Y is not reachable from X using all edges)
return -1 // No solution.
edges = a list of edges sorted by their weight in increasing order
low = -1 // definitely to small(no edges)
high = edges.length - 1 // definitely big enough(all edges)
while (high - low > 1)
mid = low + (high - low) / 2
g = empty graph
for i = 0...mid
g.add(edges[i])
if (g.hasPath(X, Y)) // Checks that there is a path using DFS or BFS
high = mid
else
low = mid
return edges[high]
1 回答
这是一个简单的解决方案：
按重量对边缘进行排序 .
开始逐个添加它们（从最轻到最重），直到
X和Y连接 .要检查它们是否已连接，您可以使用union-find数据结构 .
时间复杂度是
O(E log E).证明正确性：
正确答案不大于此解决方案返回的答案 . 情况就是这样，因为解决方案是建设性的：一旦
X和Y在同一个组件中，我们就可以明确地记下它们之间的路径 . 它不能包含较重的边缘，因为它们尚未添加 .正确答案不小于此解决方案返回的答案 . 假设
X和Y之间存在一条路径，该路径由权重严格小于返回答案的边组成 . 但是不可能，因为之前处理了所有较轻的边缘（我们以排序的顺序迭代它们）并且X和Y处于不同的组件中 . 因此，它们之间没有路径 .1）和2）暗示该算法的正确性 .
此解决方案适用于无向图 .
这是一个解决定向案例问题的算法（它也适用于无向图）：
让我们按重量对边缘进行排序 .
让二进制搜索路径中最重边缘的权重（由所有边缘的排序列表中的边缘索引确定） .
对于固定答案候选
i，我们可以执行以下操作：在排序列表中添加索引最大为
i的所有边（即，所有边不比当前边重） .运行DFS或BFS以检查是否存在从
X到Y的路径 .根据此类路径的存在，在二分查找中调整左右边框 .
时间复杂度为
O((E + V) * log E)（我们运行DFS / BFSlog E次，每次都在O(E + V)时间内完成） .这是一个伪代码：