0

CLRS で説明されている BFS アルゴリズムを実装しようとしています。そして、次のものを用意してください。

#include <iostream>
#include <list>
#include <queue>
#include <string>
#include <sstream>
using namespace std;
struct Node{
    char colour;
    int numNbr;
    Node* parent;
    int distance;
    int* neighbours;
    int* costs;
    int name;
    Node(int _numNbr,int _name){
        name = _name;
        colour = 'w';
        parent = 0;
        distance = -1;
        neighbours = new int[_numNbr];
        costs      = new int[_numNbr];
        numNbr = _numNbr;
    }
};

list<Node*> bfs(Node** &nodes,int numNodes,int startNode) {
    cout << "performing BFS\n";
    for(int i = 0; i < numNodes;i++) {
        nodes[i]->colour = 'w';
        nodes[i]->parent = 0;
    }
    cout << "All nodes painted white" <<endl;
    queue<Node*> q; // segfault occurs here
    cout << "initialised a queue" << endl;
    list<Node*> l;
    cout << "initialised a list" << endl;
    nodes[startNode]->colour = 'g';
    nodes[startNode]->distance = 0;
    q.push(nodes[startNode]);
    Node* u;
    Node* v;
    while(!q.empty()){
        u = q.front();
        for(int i = 0;i < u->numNbr; i++) {
            v = nodes[u->neighbours[i]];
            if(v->colour == 'w'){
                v->colour = 'g';
                v->distance = (u->distance)+1;
                v->parent = u;
                q.push(v);
            }
        }
        l.push_front(u);
        u->colour = 'b';
        q.pop();
    }
    return l;
}

int main(){
    int nodeCount;
    cin >> nodeCount;
    cin.ignore();
    Node** nodes = new Node*[nodeCount+1];
    for(int i = 0; i < nodeCount; i++){
        .... // build up the nodes in the adjacency list
    }
    list<Node*> l = bfs(nodes,nodeCount,1);
    cout << "BFS of nodes\n";
    for(list<Node*>::iterator it = l.begin();it != l.end();it++){
        cout << (*it)->name << " ";
    }
    cout << endl;
    return 0;
}

ただし、これを実行すると、次の出力しか得られず、その後segfaultにキューが初期化されたときにa が続きます。

jonathan@debian:~/Code/cpp/dijkstra$ ./dijkstra 
3
1 2 1 3 1
2 3 1
3 1 1

performing bfs
All nodes painted white
Segmentation fault

次のコマンドでコンパイルしています。

g++ -Wall  -o dijkstra dijkstra.cpp
4

1 に答える 1

0 
list<Node*> bfs(...

あなたが戻っている間：

return l;

また、ここで参照する必要はありません。

Node** &nodes

また、ご指摘の箇所ではsegfaultは発生していませんでした。そのため、I/O バッファーはフルフラッシュされず、次のようになります。

cout << "initialised a queue" << endl;
list<Node*> l;
cout << "initialised a list" << endl;

実行されませんでした

于 2011-09-27T06:22:56.760 に答える