BFS 스패닝 트리의 결과를 preorder로 표시하는 방법

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 2 7 8 9 그 결과 선주문으로 나무를 횡단합니다. 내 코드에 대한 솔루션이 필요합니다. 어떻게 제 코드를 수정하여 사전 순서에 따라 솔루션을 표시 할 수 있습니까? 트리를 사용하지 않아도됩니다. 즉, 배열에 BFS_tree 트리를 직접 저장하면됩니다. 나는 이것으로 붙 들렸다. here 비슷한 질문을 읽을 수 있지만 효율성 측정을 위해 트리를 구현할 수 없으며 허용되지 않습니다. 내가 어떻게 할 수 있니? 그게 가능 할까? ... 실례합니다.

Answer 1

트리의 선주문 통과는 하위에 앞서 각 상위를 처리하는 것으로 구성됩니다. 트리를 어떻게 지나가는가에 따라 다른 선주문 통과가 발생합니다. 보여준 두 탐색 모두 트리에 대한 올바른 선주문 순회입니다. 전자는 너비가 큰 첫 번째 나무 중 하나와 비슷하지만 후자는 깊이 우선 검색 순서처럼 보입니다. 너비가 큰 첫 번째 검색의 결과로 후자의 순서를 생성해야한다면 그래프의 트리 구조를 첫 번째 경로로 표시 한 다음 깊이 우선 검색을 사용하여 노드를 처리해야합니다.