C++ Breadth first search

C++ Breadth first search

                       Breadth first search

Traversal means visiting all the nodes of a graph. Breadth First Traversal or Breadth First Search is a recursive algorithm for searching all the vertices of a graph or tree data structure.

BFS algorithm

A standard BFS implementation puts each vertex of the graph into one of two categories:

  1. Visited
  2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

The algorithm works as follows:

  1. Start by putting any one of the graph's vertices at the back of a queue.
  2. Take the front item of the queue and add it to the visited list.
  3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the back of the queue.
  4. Keep repeating steps 2 and 3 until the queue is empty.

The graph might have two different disconnected parts so to make sure that we cover every vertex, we can also run the BFS algorithm on every node

//Here goes the code

#include <iostream> #include <list> using namespace std; class Graph { int numVertices; list<int>* adjLists; bool* visited; public: Graph(int vertices); void addEdge(int src, int dest); void BFS(int startVertex); }; Graph::Graph(int vertices) { numVertices = vertices; adjLists = new list<int>[vertices]; } void Graph::addEdge(int src, int dest) { adjLists[src].push_back(dest); adjLists[dest].push_back(src); } void Graph::BFS(int startVertex) { visited = new bool[numVertices]; for (int i = 0; i < numVertices; i++) visited[i] = false; list<int> queue; visited[startVertex] = true; queue.push_back(startVertex); list<int>::iterator i; while (!queue.empty()) { int currVertex = queue.front(); cout << "Visited " << currVertex << " "; queue.pop_front(); for (i = adjLists[currVertex].begin(); i != adjLists[currVertex].end(); ++i) { int adjVertex = *i; if (!visited[adjVertex]) { visited[adjVertex] = true; queue.push_back(adjVertex); } } } } 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); return 0; }