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

ツリーの事前順序トラバーサルは、子の前に各親を処理することで構成されます。ツリーをどのようにトラバースするかによって、異なる事前順序トラバーサルが得られます。あなたが示した両方のトラバーサルは、ツリーの正しい事前順序トラバーサルです。前者は幅優先ツリーの 1 つのように見えますが、後者は深さ優先検索順序のように見えます。幅優先検索の結果として後者の順序を作成することになっている場合は、グラフ内のツリー構造を最初のパスとして示してから、深さ優先検索を使用してノードを処理する必要があります。

于 2012-01-18T13:31:43.217 に答える