如何使BFS生成樹的結果顯示在預先訂購

我試圖實現BFS算法的作業，我發現生成樹算法與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 7 5 6 8 9]。表示由打印每級的節點的BFS樹如圖此圖像中：

enter image description here

但是正確的輸出（在序）應，[0 1 3 4 5 6 2 7 8 9] ，導致以預定的順序遍歷樹。我需要一個針對我的代碼的解決方案，如何修復我的代碼以便向我展示解決方案，以便不必使用樹，也就是說，可以以某種方式直接以預先排序的方式將其存儲在我的數組BFS_tree樹中。我堅持這一點。我讀了一個類似的問題here，但我無法實現樹效率的措施，這是不允許的。我怎麼能這樣做？有可能嗎？......請原諒我的英語。

來源

2012-01-18 AndrewRelex

不好意思爲圖片的外部鏈接，請編輯，因爲作爲新用戶不會讓我附上圖片 – AndrewRelex 2012-01-18 08:28:32

不應該結果是'[5 6 4 1 8 9 7 2 3 0]'，即先訂先訪問左子節點？ – arne 2012-01-18 08:50:19

不，先行順序訪問根左子女右子女 – AndrewRelex 2012-01-18 08:58:26

樹的前序遍歷包括處理每個父元素之前的子元素。根據你如何遍歷樹，你會得到不同的預先遍歷。你展示的兩個遍歷都是樹的正確前序遍歷。前者看起來像廣度優先的樹之一，而後者看起來像深度優先的搜索順序。如果您應該根據寬度優先搜索創建後一個順序，則需要將圖中的樹結構指示爲第一條路徑，然後使用深度優先搜索來處理該節點。

來源

2012-01-18 13:31:43

如何使BFS生成樹的結果顯示在預先訂購

回答

相關問題