0

これを解決するための適切なアルゴリズムを見つけようとしています: いくつかの (有向グラフ) ノードがあるとします。各ノードには、親がある場合とない場合があります (つまり、最大で 1 つの親)。ノードの表記を (id, id_parent) とします。一部のノードは (id_i, NULL) になりますが、ノード (id_j, id_i) は id_i の「息子」として存在します。これらのノードの配列を特定の順序で持っているので、それらを次の順序で並べ替えたいと思います: 親-息子-息子の息子-息子-息子の息子など.

例: ノード (1, NULL)、(2,NULL)、(3,1)、(4,3)、(5,2)、(6,3)

ソートされた配列は (1,NULL)、(3,1)、(4,3)、(6,3)、(2, NULL)、(5,2) になります。一種の詳細なツリー探索。

これを達成するのに適したアルゴリズムはどれですか? ありがとう

4

1 に答える 1

2

グラフにサイクルがない場合は、DAGであり、トポロジカル ソートを探しています。

サイクルがある場合、そのような順序付けはありません。サイクルにはノードがあり、その息子がその祖先でもあるからです。

編集: グラフがフォレスト (ツリーのばらばらの結合) の場合、ソースからの単純なDFSで十分です。グラフを作成するだけです（O(nlogn)まだソートされていない場合はソートするか、基数ソートO(n)を使用します）、ソースのリストを見つけ、各ソースからDFSを実行し、ノードにアクセスするたびに出力に保存します配列。未発見の頂点がある間繰り返す。

于 2012-05-06T16:28:06.143 に答える