したがって、エッジが最小スパニングツリーにあるかどうかを判断することは、エッジが特定のサイクルの最も重いエッジであるかどうかという問題にまで減らすことができるようです。DFSを使用して、エッジがサイクル内にあるかどうかを検出する方法を知っていますが、それがそのサイクルで最も重いエッジであるかどうかを判断する方法はありますか？サイクルを見つけて、その中で最も重いエッジを選択するだけですか？
3228 次
1 に答える
6
すべてのエッジに異なる重みがあると仮定すると、これを行うための単純でかなり洗練されたアルゴリズムは、変更されたDFSを実行することです。このエッジが特定のサイクルで最も重いエッジである場合、現在のエッジより重いすべてのエッジを削除して形成されたグラフを見ると、エッジの端点から開始点に戻るパスが必要であることに注意してください。エッジは、このパスがエッジ自体と組み合わされて、指定されたエッジが最も重いエッジであるサイクルを形成するためです。逆に、特定のエッジが最も重いエッジを含むサイクルがない場合、このグラフでエッジの端からソースまで検索を実行すると、元に戻すことはできません。エッジのソースに移動します。そうしないと、サイクルに完了する可能性があります。これにより、次の単純なアルゴリズムが得られます。エッジのエンドポイントからソースに戻る元のグラフでDFSを実行しますが、元のエッジより重いエッジに遭遇した場合は、それを処理しないでください（これはグラフからの削除をシミュレートします）。DFSがエッジの端からソースに戻る場合は、エッジが最も重いエッジであるサイクルが必要であることがわかります。そのようなサイクルがない場合は、取得できません。エッジのソースに戻ります。
エッジが明確でない場合は、上記と同じ検索を行いますが、現在のエッジの重み以上の重みを持つすべてのエッジを削除します。この理由は、この変換されたグラフにエッジの終わりからエッジの始まりまでのパスがある場合、同じコストのエッジを使用することにならないという事実を知っているからです。元のエッジであるため、見つかったパスはすべて、指定されたエッジが最も重いサイクルに完了することができます。パスがない場合は、
- 指定されたエッジを含むすべてのサイクルには、それよりも厳密に重いエッジがあります。
- 指定されたエッジを含むすべてのサイクルには、それと同じコストのエッジがあります。
どちらの場合でも、それはサイクルの中で最も重いエッジではありません。
このアルゴリズムの実行時間はO（m + n）で、標準のDFSを実行するのに必要な時間です。
お役に立てれば！
于 2012-03-04T00:31:03.730 に答える