使用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函数中的迭代器语句引起了错误。请帮我解决代码中的问题。

谢谢！

- Pranav Arora

---

编译器（根据定义）不能给您运行时错误 - 您尝试过调试程序吗？ - MikeMB

@MikeMB：抱歉，我应该更具体地说明。编译器是指我正在使用CodeChef的在线编译器。 - Pranav Arora

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;
}

我将留下最终值的计算交给您，因为我想您希望除了始终返回零之外还有其他结果。然而，这是您问题的症结所在。

祝您好运。

- WhozCraig

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);


}

- Tunvir Rahman Tusher

Answer 3

我使用STL实现了C++中的BFS算法。希望这段代码能对你有所帮助。谢谢。

#include <bits/stdc++.h>
using namespace std;
#define inf 1<<28
vector <int> G[100];
int dist[100];
int parent[100];
int distance[100];
bool visit[100];

void Display(queue <int> Q, int sz){
    for(int i=0;i<sz;i++){
        cout<< Q.front() << " " ;
        Q.pop();
    }
    cout<< endl;
}

int BFS(int source, int destination){
    queue <int> Q;
    memset(dist,inf,sizeof dist);
    Q.push(source);
    dist[source] = 0;
    visit[source] = true;

    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        for(size_t i=0;i<G[u].size();i++){
            int v = G[u][i];

            while(!visit[v]){
                dist[v] = dist[u] + 1;
                visit[v] = true;
                parent[v] = u;
                Q.push(v);
            }
        }
        cout<< "Queue Operation : " << endl;
        Display(Q,Q.size());
    }
    return dist[destination];
}


int main() {
    int node,edge;
    cin>>node>>edge;
    for(int i=0;i<edge;i++){
        int x,y;
        cin>> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    cout<< endl;

    int s,d;
    cout<< "Source & Destination : " << endl;
    cin>> s>> d;
    cout<< "Distance : " << BFS(s,d) << endl;

    cout<< "Path : " << endl;
    while(d!=s){
        cout<< d << " ";
        d = parent[d];
    }

    return 0;
}

/*
10 13
1 2
1 4
1 3
2 6
4 7
3 7
3 8
6 10
7 9
8 7
8 5
9 10
5 10
*/

- Md. Rezwanul Haque