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

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

0 голосов
/ 18 января 2012

Я пытаюсь реализовать алгоритм 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 дерево непосредственно в предзаказе. Я застрял с этим. Я прочитал аналогичный вопрос здесь , но я не могу реализовать деревья для мер эффективности, и это не разрешено. Как я мог это сделать? это возможно? ... Извините за мой английский.

1 Ответ

0 голосов
/ 18 января 2012

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

...