8

ここで私の深みから少し離れており、友人に電話する必要があります。トラバースする必要がある有向非循環グラフがあり、初めてグラフ理論に出くわしています。私は最近それについてたくさん読んでいますが、残念ながら私はこれを学術的に理解する時間がありません. このツリーを処理する方法について、誰かが助けてくれますか?

ルールは次のとおりです。

  • n 個のルート ノードがあります(私はそれらを「ソース」と呼びます)
  • n個のエンドノードがあります
  • ソースノードは数値を運ぶ
  • 下流のノード (私は「ワーカー」ノードと呼んでいます) は、追加、多重化などの受信値に対してさまざまな操作を実行します。

以下のグラフからわかるように、ノードa、b、およびは、 、、または のc前に処理する必要があります。def

この木を歩く正しい順番は？

ここに画像の説明を入力

4

2 に答える 2

7

トポロジカルソートで達成できるはずのDAGの線形化を検討します。

私が覚えていることから、線形化は基本的に、他の特定のノードに対して出次数を持つすべてのノード (Node_X) に対してが前NodeAにNodeX現れるという不変条件を保持する順序でソートしますNodeA。

これは、あなたの例から、ノード a、b、および d が最初に処理されることを意味します。ノード c 秒。ノード e と f、最後。

http://en.wikipedia.org/wiki/Topological_sorting

于 2011-08-08T22:01:09.247 に答える
5

トポロジカル ソートを介してノードを処理する必要があります。並べ替えは必ずしも一意であるとは限らないため、複数の利用可能な順序が存在する可能性があります (これは問題ではありません)。

リンクされたウィキペディアのページには、役立つ具体的なアルゴリズムが必要です。

于 2011-08-08T21:59:54.213 に答える