訪問先、親、距離のベクトルのみがある場合は予約注文ツリーウォーク

Question

primのアルゴリズムを隣接行列グラフに実装しました。このアルゴリズムの結果は、visited,parentおよびdistanceベクターの3つのベクトルである。アルゴリズムvisited[i] == trueの最後には、すべてi = 0..N-1です。 parent[i]はiの親であり、distance[i]はparent[i]からiまでの距離です。

ここで、これらの3つのベクトルを考えて、深さ優先検索を適用できるツリー構造を作成することなく、深さ優先探索ができるかどうかを考えていました。

dfsは、最小スパニングツリーを構築するために選択した最初のノードから開始する必要があります。このノードをノード0にすることを選択しました。問題は、いったんこのノードにいると、すべてのノードを反復してその親をチェックしない限り、どのノードがその子であるのかわからないことです（上の3つのベクトルのみ）。その場合、ノードiの子のセットCが与えられた場合、私はのようにC_iを選ぶべきです。

いつ停止する必要がありますか？ノードiに|C| = 0（つまり、子なしのノード）がある場合。その場合、私はiの親に戻って、まだ訪問していない子供がいるかどうかを調べることができます。

私たちが訪問するたびに訪問したノードをマーキングするという問題もあります。私はすでに再帰されたノードを追跡する別のベクトルを単純に持つことができると思う。

また、訪問した順序のリストを保持する必要があります。これは、繰り返し実行するたびにノードをリストに追加するだけの問題です。

予約注文のツリーウォークをどのように表しますか？これは、単に私が言及したノードのリストにする必要があります。 （右？）

これは間違いありませんか？それは良いアプローチですか？あなたは他のより良いアプローチを知っていますか？

Answer 1

ここで、これらの3つのベクトルを考えて、深さ優先検索を適用できるツリー構造を作成する必要なしに、深さ優先検索を実行できるかどうかを考えていました。

あなたは簡単にDFS-横切ることができると予想Θでスパニングツリーのみparentアレイを使用して時間（| | V）。

1. ノードのリンクリスト（空リストに初期化されたeacg）に対するノードIDの辞書childrenを作成します。
2. parentアレイをスキャンし、parent[i] = jの場合は、i~children[j]を追加します（リコールはリストです）。擬似コードで

：

children = dictionary of nodes to lists 
for i in 1, ..., len(parent): 
    children[parent[i]].add(i)   

定義により、Jが最小スパニングツリーのIの親である場合は、私がJの子の1つです。 childrenを構築することは、長さがparentの線形時間であると予想されます。

（次の定義MST-DFS有する）MST-DFS(0)は現在DFS順にノードを呼び出す呼び出し：

MST-DFS(j): 
    print j # Current node in DFS order 
    for i in children[j]: 
     MST-DFS(i) 

この部分を実行するparentの長さに線形です。