クラスカルのアルゴリズムでのパス情報の保存

Question

クラスカルのアルゴリズムを使用して最小全域木を生成しましたが、パスを保存する方法を知りたいと思いました

これは私の最小スパニングツリーです ジェネラコディセタグプレ

Answer 1

それはあなたがどれだけ余分なスペースを持っているかに依存します。スペース効率が良い必要があると仮定します：

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内の各ノードのルックアップ時間を想定しています）。