Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Breadth First Graph Traversal

Explore how to implement breadth first graph traversal in C++ using both iterative and recursive approaches. Understand BFS concepts, avoid revisiting nodes with visited tracking, and analyze time complexity to master graph traversal techniques.

We'll cover the following...

Solution #1: Iterative

In this algorithm, we begin from a selected node (it can be a root node) and traverse the graph layerwise (one level at a time). All neighbor nodes (those connected to the source node) are explored, then we move to the next level of neighbor nodes.

Simply, as the name Breadth First suggests, we traverse the graph by first moving horizontally and visiting all the nodes of the current layer, then moving to the next layer.

C++
#include "Graph.h"
void Graph::breadthFirstTraversal(int source) {
  vector < bool > visited(this -> vertices, false);
  list < int > queue;
  visited[source] = true;
  queue.push_back(source);
  // Get all adjacent vertices using iterator for list
  list < int > ::iterator i;
  while (!queue.empty()) {
    source = queue.front();
    cout << source << " ";
    queue.pop_front();
    for (i = adjacencyList[source].begin(); i != adjacencyList[source].end(); ++i) {
      if (!visited[ * i]) {
        visited[ * i] = true;
        queue.push_back( * i);
      }
    }
  }
}
int main() {
  Graph g(6);
  g.addEdge(0,1);
  g.addEdge(1,2);
  g.addEdge(1,3);
  g.addEdge(2,4); 
  g.addEdge(3,4); 
  g.addEdge(3,5);
  g.breadthFirstTraversal(0);
  return 0;
}

Psuedocode

Let’s have a look at the pseudocode of breadth-first traversal:

Input: root is a node in the graph
Output: all nodes visited in breadth-first order

breadthFirstTraversal(source)
  Let q = queue
  while source != ø
    print source
    for all adjacent vertices v of source
      q.enqueue(v)

    if !q.isEmpty()
      source = q.dequeue()
    else
      source = ø

Avoid Visiting the Same Nodes Again!

A graph may contain cycles, which will lead to visiting the same node again and again while we traverse the graph. To avoid processing the same node again, we can use a boolean array that marks visited array.

To make this process easy, use a queue to store the node and mark it as visited until all its neighbors (vertices that are directly connected to it) are marked.

The queue follows the First In First Out (FIFO) queuing method. Therefore, neighbors of the node will be visited in the order in which they were inserted in the queue; i.e. the node that was inserted first will be visited first, and so on.

Remember to mark all ∣V∣|V| vertices as not-visited before running the algorithm.

Also, have a look at how built in C++ list is iterated. You can find the documentation here.

list <int> ::iterator i;
    for (i = adjacencyList[source].begin(); i != adjacencyList[source].end(); ++i) {
      }

Time Complexity

The time complexity of BFS can be computed as the total number of iterations performed by the for loop in the code above

Let EE be the set of all edges in the connected component visited by the algorithm. For each edge u,v{u, v} in EE the algorithm makes two for loop iteration steps: one time when the algorithm visits the neighbors of uu, and one time when it visits the neighbors of vv.

Hence, the time complexity is OO(∣V∣|V| ++ ∣E∣|E|).

Solution #2: Recursive

C++
#include "Graph.h"
void Graph::utilityFunction(list <int> &queue, bool *visited){
  list <int> ::iterator i;
  while (!queue.empty()) {
    int source = queue.front();
    cout << source << " ";
    visited[source] = true;
    queue.pop_front();
    for (i = adjacencyList[source].begin(); i != adjacencyList[source].end(); ++i) {
      if (!visited[ * i]) {
        visited[ * i] = true;
        queue.push_back( * i);
      }
    }
    utilityFunction(queue, visited);
  }
}
void Graph::breadthFirstTraversal(int source) {
  bool * visited = new bool[this -> vertices];
  for (int i = 0; i < this -> vertices; i++)
    visited[i] = false;
  list <int> queue;
  visited[source] = true;
  queue.push_back(source);
  
  utilityFunction(queue, visited);
  delete(visited);
}
int main() {
  Graph g(6);
  g.addEdge(0,1);
  g.addEdge(1,2);
  g.addEdge(1,3);
  g.addEdge(2,4); 
  g.addEdge(3,4); 
  g.addEdge(3,5);
  g.breadthFirstTraversal(0);
  return 0;
}

In the recursive solution, we write a utilityFunction() that helps us perform recursion.

As shown by the highlighted text, we call the utility function starting from source vertex and then recursively call this function again for all the nodes in the queue. Since the queue is a first in first out (FIFO) data structure, the vertex v that is first pushed in the queue is processed first.

Pseudocode

breadthFirstTraversal(source):
  Queue q;
  q.push(source);
  utilityFunction(q)

utilityFunction(Queue q):
  if q.empty() return;

  Node u = q.pop()
  print u
  for all adjacent vertices v of u
     if q.push(v)

  utilityFunction(q) //recursion here.

Time Complexity

The time complexity of Breadth First Iterative Traversal and Breadth First Recursive Traversal remains the same; O(V+E)O(V+E) because we are traversing the entire graph once.