Как сделать результат связующего дерева BFS показан в preorder

Question

Я пытаюсь реализовать алгоритм BFS для домашней работы, я нахожу алгоритм spanning tree с 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 3 4 5 6 2 7 8 9] , в результате чего дерево перемещается в предварительном порядке. Мне нужно решение для моего кода. Как можно исправить мой код, чтобы показать мне решение в предзацибе ?, для того, чтобы не использовать деревья, то есть, так или иначе, можно каким-то образом сохранить в моем массиве BFS_tree дерево непосредственно в предварительном порядке. Я застрял в этом. Я прочитал аналогичный вопрос here, но я не могу реализовать деревья для мер эффективности, и это запрещено. Как я могу это сделать? это возможно? ... Извините мой английский.

Answer 1

Обход предварительного дерева дерева состоит из обработки каждого родителя до его дочерних элементов. В зависимости от того, как вы пересекаете дерево, вы получаете разные обходные пути. Оба обхода, которые вы показали, являются правильными обходами предзаказов для дерева. Первый выглядит как один из широких первых деревьев, а последний выглядит как первый порядок поиска глубины. Если вы должны создать последний порядок в результате первого поиска ширины, вам нужно указать древовидную структуру в графе в качестве первого пути, а затем обработать узел, используя первый поиск глубины.