java - MSTで最大の重み付きエッジを見つけるにはどうすればよいですか？

Question

タイトルは非常に簡単です。

私は、V頂点を持つ重み付けされたエッジで無指向の既存のMSTを持っています。与えられた開始ノードと終了ノードには、O(V)の時間で実行される効率的なアルゴリズムがMSTの最大の重みを返しますか？

ありがとうございます！

Answer 1

既存のMSTで修正BFSを使用できます。 グローバル変数maxWeightを維持します。ここにループがないので、作業を完了できます。

P.S. BFSのように訪問先ノードを追跡します。