0

スパニングツリーを見つけるためにC++でBFSアルゴリズムの実装を行っています。スパニングツリーの出力は事前に表示する必要がありますが、実装に疑問があります。正確にわからない場合にツリーを構築する方法多くの子供が各ノードを持っていますか？ツリー構造を再帰的に検討するツリーのデータ構造は次のように記述できます。

typedef struct node 
{
        int val;
        struct node *left, *right;
}*tree; //tree has been typedefed as a node pointer.

ただし、前述のようにこの実装が機能するとは思わないでください。

これは、ツリーを事前順序で返すための私の関数です。

void preorder(tree t) 
{
        if(t == NULL)
                return;
        printf("%d ", t->val);
        preorder(t->left);
        preorder(t->right);
}

また、ツリー構造を使用せずにノードの事前順序付けを行う方法はないかと思います。

4

1 に答える 1

3

私は投稿で2つの具体的な質問を見ました：

  1. ツリー内で3つ以上の子を使用するデータ構造を持つことは可能ですか？もちろん、これは可能です。興味深いことに、投稿したノード構造でも可能です。leftポインタを最初の子へのrightポインタであり、次の兄弟へのポインタであると考えてください。グラフの幅優先探索は暗黙的にスパニングツリーを構築するため、実際に何らかの方法で表現する場合は、このツリーを事前に順序付けて歩くことができます。
  2. ツリー構造を使用せずにプレオーダーウォークを実行できますか？はい、これも可能です。基本的に、DFSとBFSは概念的には違いはありません。次にアクセスするノードを維持するデータ構造があるだけです。DFSの場合、これはスタックであり、BFSの場合、これはキューです。訪問するノードを維持するデータ構造にノード番号を挿入するときにノード番号を発行すると、ツリーの事前順序ウォークが得られます（つまり、親の後にノードのすべての子を訪問します）。

2番目のポイントを少し拡張するには：木の事前注文ウォーク単に、各ノードが子ノードの前に処理されることを意味します。グラフの連結成分をトラバースするグラフ検索を実行し、各ノードに1回だけアクセスすると、暗黙のツリーが効果的に作成されます。つまり、開始ノードがツリーのルートノードになります。ノードにアクセスするたびに、アクセスされていない、つまりマークされていない隣接ノードを検索します。そのようなノードがある場合、インシデントエッジはツリーノードになり、ノードにマークを付けます。アクティブに保持されているノードは常に1つだけなので、処理されていないノードを覚えておく必要がありますが、スタックやキューなどの一部のデータ構造では（スタックを明示的に使用する代わりに、再帰を実行して、暗黙的にスタックします）。今、

これがわからない場合は、紙を一枚取り出してグラフとキューを描いてください。

  • 白丸のノードとその横のノード番号
  • 細い線のあるエッジ
  • キューは単なる長方形で、最初は何も含まれていません

次に、ツリーのルートノードと同じノードを選択して検索の開始ノードにします。その番号をキューの最初の空の位置に書き込み、マークを付けます。つまり、ノードを埋めます。次に検索を続行します。

  • キューの前に示されているノードを見て、満たされていない隣接ノードを見つけます。
    • キューの後ろ（つまり、長方形の最後のノードのすぐ後ろ）にノードを追加します
    • ノードにマークを付ける（つまり塗りつぶす）
    • 2つのノードを結ぶ線を太くします。これは木の端になります
  • マークされていない隣接ノードがそれ以上ない場合は、キュー内のフロントノードにチェックマークを付け（つまり、キューから削除し）、ノードがなくなるまで次のノードに移動します。

これで、キューの長方形には、グラフの幅優先探索によって示されるスパニングツリーのプレオーダーウォークが含まれます。スパニングツリーは、太い線を使用して表示されます。キューの長方形をスタックとして扱った場合にもアルゴリズムは機能しますが、まだ処理されていないノード間のノードがチェックされてしまうため、少し面倒になります。最初のチェックされていないノードを見る代わりに、最後にチェックされていないノード。

グラフアルゴリズムを使用する場合、アルゴリズムを視覚化することが非常に役立つことがわかりました。コンピューターに描画を維持させるのは良いことですが、紙に物を描画し、ラベルの付いた鉛筆の数でアクティブなノードを示すというローテクの代替手段も、うまくいかない場合でも機能します。

コードにコメントするだけです。入力を読み取るときは常に、データが正常に読み取られることを確認してください。ところで、あなたのコードは明らかにCのみであり、C++コードではありません。可変長配列はC++では使用できません。C ++std::vector<int> followOrder(vertexNumber)では、の代わりにを使用しますint followOrder[vertexNumber]。興味深いことに、コードはたとえばを使用しているため、Cでもありませんstd::queue<int>。

于 2012-01-15T01:33:13.760 に答える