-1

Kruskal アルゴリズムを使用してこの最小スパニング ツリーを生成しましたが、2 つのノード間のパスを生成するのに苦労しました。誰かが擬似コードで私を助けることができますか? Adjacency List と Adjacency Matrix を使ってみた

Loc1 |  Loc2 |  Distance
  02 |   10  |    2.00 Km
  05 |   07  |    5.39 Km
  02 |   09  |    5.83 Km
  04 |   05  |    5.83 Km
  06 |   08  |    5.83 Km
  03 |   09  |    7.07 Km
  01 |   04  |    11.18 Km
  07 |   09  |    11.18 Km
  07 |   08  |    15.81 Km
Total Weight = 70.12 Km
----------------------------------------------------
4

2 に答える 2

1

2 つのノード間の任意のパスのみが必要な場合は、幅優先検索が実行され、最短パスが生成されます (最小スパニング ツリーであるため)。

于 2012-02-22T05:05:31.747 に答える
0

定義上、スパニング ツリーにはサイクル (またはループ) がないため、2 つのノード間に最大で 1 つのパス (つまり、「パス」ではなく、複数形) しか持つことができません。

おそらく私は質問を理解していません。ツリー内で特定の 2 つのノードがどのように接続されているかを見つけようとしていますか?

もしそうなら、おそらくスタックから可能性をプッシュしてポップすることによって、可能性のあるエッジに沿って1つのポイントからたどるという、これに関する最も単純なブルートフォースのように思えますが、最悪の場合のO(Edges)ランタイムになります。これは、クルスカルのアルゴリズムと比較して些細なことです。もっと速いものが必要ですか？

于 2012-02-22T05:04:43.647 に答える