Algorithms for Coding Interviews in C++/

...

/

Solution: Breadth First Graph Traversal

Solution: Breadth First Graph Traversal

In this review, we will learn how to write code for the Breadth-First Traversal of a Graph.

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.

Press + to interact
main.cpp
Graph.cpp
Graph.h
#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 ...

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy