使用STL在C++中实现图形和BFS

Question

以下是我写的代码.

#include <iostream>
#include <vector>
#include <list>
#include <queue>

using namespace std;

const int V=5;
vector<list<int> > a(V);

int BFS(int s)
{
    int visited[V]={0};
    queue<int> Q;
    visited[s]=1;
    Q.push(s);
    while(!Q.empty())
    {
        int x=Q.front();
        vector<list<int> >::iterator it1=a.begin()+x;
        list<int> it2=*it1;
        list<int>::iterator iter=it2.begin();
        while(iter!=it2.end())
        {
            if(visited[*iter]==0)
            {
                visited[*iter]=1;
                Q.push(*iter);
            }
            visited[x]=2;
            Q.pop();
            iter++;
        }
    }
    return 0;
}

void addEdge(int i, int j)
{
    a[i].push_back(j);
    a[j].push_back(i);
}

int main() {
    vector<list<int> >::iterator it1=a.begin();
    addEdge(0,1);
    addEdge(0,2);
    addEdge(2,1);
    while(it1!=a.end())
    {
        list<int> it2=*it1;
        list<int>::iterator iter=it2.begin();
        while(iter!=it2.end())
        {
            cout<<*iter<<" ";
            iter++;
        }
        cout<<endl;
        it1++;
    }
    cout<<BFS(0);
    return 0;
}

执行BFS(0)时,编译器给出了运行时错误.由于我对迭代器没有太多经验,我认为错误来自BFS函数中的迭代器语句.请帮我解决代码中的问题.

谢谢!

Answer 1

你的流行逻辑错了.它应该如下所示:

int BFS(int s)
{
    int visited[V]={0};
    queue<int> Q;
    visited[s]=1;
    Q.push(s);
    while(!Q.empty())
    {
        int x=Q.front();
        Q.pop(); // pop here. we have x now

        vector<list<int> >::iterator it1=a.begin()+x;
        list<int> it2=*it1;
        list<int>::iterator iter=it2.begin();
        while(iter!=it2.end())
        {
            if(visited[*iter]==0)
            {
                visited[*iter]=1;
                Q.push(*iter);
            }
            ++iter;
        }

        visited[x]=2; // set visited here.
    }
    return 0;
}

计算我留给你的最终价值,因为我想你想要的东西总是被归还.然而,这是你的问题的关键.

祝你好运.

Answer 2

我希望这段代码会有所帮助

#include <iostream>
#include <list>
#include<queue>

using namespace std;

class Graph{

    int nodes;
    list<int>*adjMat;
    bool *visited;
public:
    Graph(int n){

        this->nodes = n;
        this->adjMat = new list<int>[n];
        this->visited = new bool[n];
    }

    void addEdge(int u,int v){

        this->adjMat[u].push_back(v);
    }
    void bfs(int n);

};


void Graph:: bfs(int n){

    for(int i=0;i<this->nodes;i++)
        visited[i]=false;

    list<int>::iterator it;

    queue<int>q;
    q.push(n);
    while (!q.empty()) {

        int currentNode = q.front();
        visited[currentNode] = true;
        cout<<currentNode<<" ";
        q.pop();
        for(it=adjMat[currentNode].begin();it!=adjMat[currentNode].end();it++){

            if(!visited[*it]){

                q.push(*it);
            }

        }

    }

}

int main(){

    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    g.bfs(2);


}