algorithm - 祖先を見つけるアルゴリズム

Question

これは試験で出題されました。解決策を見つけるのを手伝ってもらえますか?

以下を使用して、(ツリーまたはグラフの) 特定のノードの祖先の数を見つけるアルゴリズムを設計します。

1. O(m) メモリ
2. 無制限のメモリサイズ

Answer 1

グラフにサイクルがないと仮定すると (この場合、祖先は意味をなしません)、DFS ループを使用して任意のノード k の祖先を計算できます。各反復でカウントされたノードをマークするだけで、訪問したノードを 2 回カウントしません。

for i in graph visited[i] = false // for DFS

for i in graph counted[i] = false // for ancestors

int globalcount = 0; // count the no of ancestors

for i in graph DFS(i,k) //DFS-loop

def bool DFS(u,k) {   //K is the node whos ancestors want to find


if(!visited[u]) {

visited[u] = true // prevent re-entering

totalret = false // whether there is path from u to k

for each edge(u,v) {

retval = DFS(v)

if(retval&&!counted[u]&&u!=k) {  //there is path from u to k & u is not counted 

  globalcount++

  counted[u] = true

  totalret = true

}

}

if(u == k) return true

else return totalret

}

return counted[u] // if visited already and whether ancestor(k)?
}

print globalcount // total ancestor(k)

空間の複雑さ : O(V)V : 頂点の数

時間計算量 : O(E) E : グラフのエッジの数

Answer 2

アルゴリズムは、ツリーの設計に依存します。最も単純な例は、親を含むノードの場合です。この場合、

int ancestors = 0;
while( node = node->parent) ancestors++;

合理的な実装では、制約は問題になりません。

ノードに親が含まれていない場合は、ツリーの構造に依存します。

• 順序付けられていないツリーの最も複雑なケースでは、祖先をカウントする完全なツリー検索が必要になります。
• 検索ツリーの場合、必要なのは検索を行うことだけです。