スパニングツリーの最小限の問題は正しい解決法ですか？

Question

私は試験からの質問があり、私のアプローチがこの質問に適しているかどうかを知りたいと思います。

Input: graph G(V,E),weight function f:E->R and edge e=(u,v). 
output: algorithm that finds a minimum spanning tree with edge e in it. 

私のソリューションクラスカルのアルゴリズムを実行し、それが存在しない場合は、エッジeを追加することで、それは木がn-1のエッジであるので、我々は、円を通過して円を作り、最大のエッジを削除する必要があります（その円に存在するものではありません。

は私の解決策ですか？もしそれがあればそれを証明する方法、誰かがなぜ私に教えてくれるのですか？

（PS私はこの質問のためのソリューションは、ちょうど私のアプローチが正しいかどうかを知りたいき）

Answer 1

またはその他の方法かもしれない、PrimまたはKruskalのアルゴリズムを使用していますが、最初のグラフにedge eを追加（ツリー内に存在しなければならないため）、その後、通常のアルゴリズムステップで優先キュー（例えば、fibonacci heap）からポップすることによって重み値の昇順でエッジを追加し続けると、アルゴリズム自体はサイクルが存在しないことを保証し、ツリーがグラフにまたがっています（サイクルをトラバースし、eとは異なる最大ウェイトエッジを削除するための余分なステップは必要ありません）。