BFSスパニングツリーの結果をあらかじめ用意されています

Question

私は宿題用のBFSアルゴリズムを実装しようとしています。私はBFSでスパニングツリーアルゴリズムを見つけましたが、結果的にスパニングツリーが必要です予約注文に表示されます。この入力用

#include <stdio.h> 
#include<iostream> 
#include <vector> 
#include <stdlib.h> 
using namespace std; 
#define MAX 10001 
#include <queue> 

int BFS_graph[MAX][MAX]; 
int followOrder [MAX]; 
queue<int> myQueue; 
int visit[MAX]; 
int V, it, it2=0; 
bool first; 
int BFS_tree [ MAX ]; 

void bfs(int root){ 
    int i, j,it2=0, node; 
    memset(visit, 0, sizeof(visit)); 
    myQueue.push(root); 
    while(!myQueue.empty()) 
    { 
      node = myQueue.front(); 
      myQueue.pop(); 
      if(visit[node]) continue; 
      visit[node] = 1; 
     // cout <<" "<<node; 
      BFS_tree[it2]=node; 
      it2++; 
       for(i=0; i<V; i++) 
       { 
       if(BFS_graph[i][node]) myQueue.push(i); 
       if(BFS_graph[node][i]) myQueue.push(i); 
       } 
    } 
} 

int main(int argc, char *argv []){ 
int origin ,destination, i, j, k; 
int vertexNumber, EdgesNumber; 

    int initial; 
    memset(visit, 0, sizeof(visit)); 

    cin>>vertexNumber>>EdgesNumber; 
     V=vertexNumber; 


     for (int j=0; j<EdgesNumber; j++){ 
      cin>>origin>>destination; 
      BFS_graph[origin][destination]=1; 
      BFS_graph[destination][origin]=1; 
     } 

     for (int j=0; j<vertexNumber; j++) 
     cin>>followOrder[j]; 

     first = true; 
     initial=followOrder[0]; 

     bfs (initial); 
     for (int j=0; j<V; ++j) 
     cout<<BFS_tree[j]<<" "; 

return 0; 
} 

：

10 10 
0 1 
0 3 
1 3 
0 2 
4 1 
4 5 
6 4 
7 2 
8 7 
7 9 
0 1 2 3 4 5 6 7 8 9 

私のアルゴリズムは、出力として生成：[0 1 2 3 4 5 6 7 8 9]ここに私の溶液コードです。このイメージに示すようにレベルごとにノードを印刷することによりBFSツリーを表す：

しかし（プレオーダーで）正しい出力は、でなければならない[0 1 2 3 4 5 6 7 8 9]その結果、ツリーをあらかじめ順番に走査します。私は私のコードの解決策が必要です、私はどのようにツリーを私の配列に格納することができますツリーを使用する必要はありません、preorderのソリューションを私のコードを修正することができますか？私はこれで固執した。私は同様の質問hereを読んでいますが、効率測定のためにツリーを実装することはできず、許可されていません。どうすればこのことができますか？それは可能ですか？...。すみません。

Answer 1

ツリーのプリオーダートラバーサルは、各子をその子の前に処理することから成ります。ツリーをどのようにトラバースするかによって、異なるプレオーダートラバーサルが発生します。あなたが示した両方のトラバーサルは、ツリーの正しいプリオーダートラバーサルです。前者は幅の広い最初の木のように見え、後者は深さの最初の検索順序のように見えます。幅広い最初の検索の結果として後者の順序を作成することになっている場合は、グラフのツリー構造を最初のパスとして指定し、深さ優先検索を使用してノードを処理する必要があります。