如何让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 7 5 6 8 9]。通过打印每个级别的节点来表示 BFS 树，如下图所示：

但正确的输出（在preorder) 应该是 [0 1 3 4 5 6 2 7 8 9]，从而以预序遍历树。我的代码需要一个解决方案，如何修复我的代码以向我显示预序中的解决方案？，因为不必使用树，也就是说，可以以某种方式直接按预序存储在我的数组 BFS_tree 中。我坚持这个。我在此处阅读了类似的问题 但我不能实施树来提高效率，这是不允许的。我怎么能这样做呢？这可能吗？...请原谅我的英语。

Answer 1

树的前序遍历包括在其子级之前处理每个父级。根据您遍历树的方式，您会得到不同的预序遍历。您显示的两种遍历都是树的正确前序遍历。前者看起来像广度优先的树，而后者看起来像深度优先的搜索顺序。如果您应该创建后一个顺序作为广度优先搜索的结果，则需要将图中的树结构指示为第一路径，然后使用深度优先搜索处理节点。