アルゴリズムを使用してスパニングツリーの事前順序を示す方法BFS

Question

スパニングツリーを見つけるために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); 
} 

ツリー構造を使用せずにノードの先行を行うにはどのような方法があるかどうか私も疑問に思います。

Answer 1

私が投稿して2つの具象の質問を見てきました：

1. は、それがツリーに以上2人の子供を使用してデータ構造を持つことは可能ですか？もちろんこれも可能です。興味深いことに、投稿したノード構造でも可能です！ leftポインターを最初の子ポインターとし、rightポインターを次の兄弟ポインターを指すポインタとみなしてください。グラフの幅広い最初の検索は暗黙的にスパニングツリーを構築するので、実際に何らかの形で表すならば、このツリーをあらかじめ順番に移動することができます。
2. ツリー構造を使用せずにプリオーダーウォークを行うことはできますか？はい、これも可能です。基本的に、DFSとBFSは概念的に違いはありません。次にアクセスするノードを維持しているデータ構造だけです。 DFSの場合、これはスタックです.BFSの場合、これはキューです。訪問先のノードを維持してデータ構造にノード番号を挿入すると、ノード番号を送信すると、ツリーのプレオーダーウォーク（親の後にあるノードのすべての子ノードを訪問します）が表示されます。

は、第二の点のビットを展開するには：ツリーの先行順徒歩だけで、各ノードが子ノードの前に処理されることを意味しています。グラフ検索を実行すると、グラフの接続されたコンポーネントを横断して各ノードに一度だけアクセスすると、暗黙的なツリーが効果的に作成されます。つまり、開始ノードはツリーのルートノードになります。ノードにアクセスするたびに、訪問していない、つまりマークされていない隣接ノードを検索します。このようなノードがある場合、インシデントエッジはツリーノードになり、ノードにマークを付けます。常にアクティブに保持されているノードは1つだけなので、処理されていないノードを覚えておく必要があります。 （スタックを明示的に使用するのではなく、スタックを暗黙的に作成する再帰を行うことはできません）。ここで、ノード番号を最初に表示すると、そのノードを子供の前に処理することを明確に示します。つまり、ノード番号を書き終えると、あらかじめ注文した順番が続きます。

あなたがこれを理解していない場合は、一枚の紙をサッと取り出し、グラフやキューを描くください

• 横に白丸およびそのノード番号を持つノード
• エッジ細い線
• でキューが開始

では何も入っていないだけで矩形が今、ルートノードと同じである、検索の開始ノードになるためにノードを選択していますあなたの木の。その番号を待ち行列の最初の空の位置に書き、マークする。ノードを埋める。今すぐ検索を続行：キューの先頭で示されたノードで

• 外観と満たされていない隣接ノードを見つける：
  • はつまり真後ろ（キューの後ろにノードを追加します矩形内の最後のノード）
  • マーク（すなわち充填）ノード
  • は、2つのノード厚いを結ぶ線を作る：さらなる隣接する非マークがある場合、それはツリーエッジ今
• ではありませんノードは、キュー内のフロントノードをオフにする。キューから削除）し、

今すぐキュー長方形がグラフの幅優先探索によって暗黙のスパニングツリーの前の散歩が含まれているそれ以上のノードが存在しなくなるまで次のノードに移動します。スパニングツリーは、太い線で表示されます。このアルゴリズムは、キューの長方形をスタックとして扱っても機能しますが、まだ扱われていないノードの間にあるノードをオフにしてしまうため、少し混乱します。最初に確認していないノードを見るのではなく最後のuntickedノード

グラフアルゴリズムを使用するとき、私はアルゴリズムを視覚化することが非常に有用であることを発見しました。コンピュータに描画を維持させることは良いことですが、紙の上に物を描き、おそらくラベルの付いた鉛筆でアクティブノードを示すという、ローテクの選択肢はうまくいきません。

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