java - 如何找到MST中最大的加權邊緣？

Question

根據標題，問題非常簡單。

我有一個現有的MST，不帶有加權邊緣，有V個頂點。給定一個起始節點和結束節點，是否有一個有效的算法在O(V)時間運行，返回MST中最大的權重？

謝謝！

Answer 1

您可以在現有的MST上使用修改後的BFS。 保持一個全局變量maxWeight，並且因爲這裏不會有任何循環，所以可以完成工作。

P.S.跟蹤BFS中訪問的節點。