C/C++ Graph Implementation using STL C++

  • Thread starter Thread starter Saitama
  • Start date Start date
  • Tags Tags
    C++ Graph
AI Thread Summary
The discussion centers on implementing a breadth-first search (BFS) algorithm in C++ for a graph represented using adjacency lists. The original code encounters a runtime error when executing the BFS function. The main issue identified is an incorrect implementation of the BFS algorithm. Key points include the need for proper marking of visited vertices and correct handling of the queue during traversal. The corrected BFS implementation ensures that each vertex is visited only once and outputs the visited vertices correctly. The discussion concludes with acknowledgment of the assistance received in resolving the issue.
Saitama
Messages
4,244
Reaction score
93
I am trying to implement a graph and perform BFS on it in C++. Following is the code I have written so far:

Code:
#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;
}

The code works fine till the point when "cout<<BFS(0)" is called. I get a runtime error when the function BFS is executed. I do not have much experience with using iterators in C++ so I believe the error comes from the iterator statements in BFS function.

Any help is appreciated. Thanks!
 
Technology news on Phys.org
Pranav,
I'm not quite sure if your question is one involving C++ iterators or the breadth first search algorithm applied to a component of a graph. However, the main problem in your code is that you have not implemented BFS correctly. Maybe you know this, but I'll repeat.

A graph consists of vertices (non-negative ints) and edges. This may be implemented with an array a of lists were a is the "adjacency" list of vertices j such that {i,j} is an edge of the graph. (For a graph (not a digraph), if j appears on list a, i appears on a[j].)

Now BFS is an algorithm with input a vertex s. The algorithm traverses (visits) all vertices in the component of the graph containing s. That is a vetex i is visited iff i is reachable from s (there is a sequence s=v0, v1, ... vn=i where a pair of adjacent vertices in the sequence is an edge of the graph).

The algorithm is implemented with a queue Q. The idea is that during the execution of the algorithm each vertex i reachable from s appears exactly once in Q. This is accomplished by initially "marking" all vertices as not visited, enqueue s and then mark s as "visited". Then
Code:
 while Q is not empty {
       remove the front vertex x from Q;
       for each vertex i adjacent to x {
             if i is not marked as visited, "visit" i, mark i as visited and add i to Q
       }
   // the above is accomplished by walking down (traversing) the adjacency list a[x]
}
The validity of the algorithm can be proved by induction on the minimal path length from s to a vertex i in the component containing s.

Here's your program with a corrected BFS:

Code:
#include <cstdlib>
#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;
   cout << " " << s << " "; // "visit" s
   Q.push(s);
   while (!Q.empty()) {
      int x = Q.front();
      Q.pop();
      list<int>::iterator iter = a[x].begin();
      while (iter != a[x].end()) {
         if (visited[*iter] == 0) {
            visited[*iter] = 1;
            // "visit" vertex *iter
            cout << " " << *iter << " ";
            Q.push(*iter);
         }
         ++iter;
      }
   }
   cout << endl;
   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;
}
 
Thank you very much johng. I found the error later but forgot to respond here. :)

Sorry for the late response.
 
Thread 'Star maps using Blender'
Blender just recently dropped a new version, 4.5(with 5.0 on the horizon), and within it was a new feature for which I immediately thought of a use for. The new feature was a .csv importer for Geometry nodes. Geometry nodes are a method of modelling that uses a node tree to create 3D models which offers more flexibility than straight modeling does. The .csv importer node allows you to bring in a .csv file and use the data in it to control aspects of your model. So for example, if you...
I tried a web search "the loss of programming ", and found an article saying that all aspects of writing, developing, and testing software programs will one day all be handled through artificial intelligence. One must wonder then, who is responsible. WHO is responsible for any problems, bugs, deficiencies, or whatever malfunctions which the programs make their users endure? Things may work wrong however the "wrong" happens. AI needs to fix the problems for the users. Any way to...
I am trying to run an .ipynb file and have installed Miniconda as well as created an environment as such -conda create -n <env_name> python=3.7 ipykernel jupyter I am assuming this is successful as I can activate this environment via the anaconda prompt and following command -conda activate <env_name> Then I downloaded and installed VS code and I am trying to edit an .ipynb file. I want to select a kernel, via VS Code but when I press the button on the upper right corner I am greeted...
Back
Top