0

我正在尝试为作业实现 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 树，如下图所示：

在此处输入图像描述

但是正确的输出（按顺序）应该是[0 1 3 4 5 6 2 7 8 9]，从而导致按顺序遍历树。我需要我的代码的解决方案，如何修复我的代码以向我显示预购解决方案？，因为不必使用树，也就是说，可以以某种方式将树直接存储在我的数组 BFS_tree 中。我坚持这一点。我在这里读到了一个类似的问题，但我不能为效率措施实施树，而且这是不允许的。我怎么能这样做？有可能吗？...对不起，我的英语。

4

1 回答 1

0

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

于 2012-01-18T13:31:43.217 回答