Реализация графа и BFS в C++ с использованием STL

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


} 

Answer 3

BFS в C++ с использованием STL, что у меня есть implemented.I надеется, что этот код будет полезным. Спасибо.

#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 
*/