java - 如何找到MST中最大的加权边缘？

Question

根据标题，问题非常简单。

我有一个现有的MST，不带有加权边缘，有V个顶点。给定一个起始节点和结束节点，是否有一个有效的算法在O(V)时间运行，返回MST中最大的权重？

谢谢！

Answer 1

您可以在现有的MST上使用修改后的BFS。 保持一个全局变量maxWeight，并且因为这里不会有任何循环，所以可以完成工作。

P.S.跟踪BFS中访问的节点。