2つのノード間のエッジの数を生成します
-
29-10-2019 - |
質問
クラスカルアルゴリズムを使用してこの最小スパニングツリーを生成しましたが、2つのノード間にパスを生成するのに苦労しています。誰かが擬似コードを手伝ってくれますか?隣接リストと隣接行列を使ってみました ジェネラコディセタグプレ
解決
2つのノード間のパスが必要な場合は、幅優先探索で十分です。最短パスを生成します(最小スパニングツリーのため)。
他のヒント
スパニングツリーには、定義上、サイクル(またはループ)がないため、2つのノード間には最大で1つのパス(つまり、「パス」ではなく、複数形)しか持てません。
おそらく私はその質問を理解していません。与えられた2つのノードがツリー内でどのように接続されているかを見つけようとしていますか?
もしそうなら、これに対する最も単純なブルートフォースのように聞こえます。おそらくスタックから可能性を押したりポップしたりすることによって、可能なエッジに沿って1つのポイントからたどるだけで、最悪の場合のO(エッジ)になります。実行時間。これは、クラスカルのアルゴリズムと比較すると簡単です。 もっと速いものが必要ですか?
所属していません StackOverflow