0

Kruskal のアルゴリズムを使用して最小全域木を生成しましたが、パスを格納する方法を知りたいと思っていました。

これは私の最小スパニングツリーです

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

1 に答える 1

2

余分なスペースがどれだけあるかによって異なります。スペースを効率的に使用する必要があるとします。

  1. 結果の構造が各ノードに対して最大で 1 つの親ノードを持つように、エッジを方向付けます。どうやってするの？ノードを選択してルートにするだけです。その子は第 1 レベルのノードなどです
  2. 結果のグラフを child->parent の形式で保存します (テーブルでは、Loc1 列を子にし、Loc2 列を親にすることができます。子でインデックスを付けます)。
  3. 距離を計算する必要がある与えられた 2 つのノード a と y について、それらの親セットを見つけ、それらが交差する場所を確認します。元。x の親が A の場合、A の親は B です... 親のパスは ABCDLMN (N はルート) です。y の親ルートが EFLMN の場合も同様です。ご覧のとおり、両方の最小共通根は L です。x->L からの距離は 5、y->L は 3、=> x と y の間の距離は 5+3=8 です。

複雑さ: O(hlogn) ここで、h はツリーの高さ、n はツリー内の要素の数です (logn の各ノードのルックアップ時間を想定しています)。

于 2012-02-21T19:39:16.870 に答える