Graph Traversal - Breadth-First Search

Introduction

Graph traversal means visiting every vertex and edge exactly once in a well-defined order. While using certain graph algorithms, you must ensure that each vertex of the graph is visited exactly once. The order in which the vertices are visited is important and may depend upon the algorithm or question that you are solving. During a traversal, it is important that you track which vertices have been visited. The most common way of tracking vertices is to mark them.

Breadth-first search approach

There are many ways to traverse graphs. Breadth-First Search (BFS) is the most commonly used approach. Breadth-First Search (BFS) is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layer-wise thus exploring the neighbor nodes (nodes that are directly connected to source node). You must then move towards the next-level neighbor nodes. As the name Breadth-First Search (BFS) suggests, you are required to traverse the graph breadth-wise as follows:

• First, move horizontally and visit all the nodes of the current layer
• Then, move to the next layer

Let’s look at the visualization below. Breadth-First Search (BFS) colors each vertex white, gray, or black. All vertices start out white and may later become gray and then black. A vertex is discovered the first time it is encountered during the search, at which time it becomes nonwhite. Gray and black vertices, therefore, have been discovered, but Breadth-First Search distinguishes between them to ensure that the search proceeds in a breadth-first manner. If (u, v) is a node pair that is connected by an edge and vertex u is black, then vertex v is either gray or black, i.e., all vertices adjacent to black vertices have been discovered. Gray vertices may have some adjacent white vertices. They represent the frontier between discovered and undiscovered vertices.

Breadth-First Search constructs a breadth-first tree, initially containing only its root, which is the source vertex. Whenever a white vertex v is discovered in the course of scanning the adjacency list of an already discovered vertex u, the vertex v and the edge (u, v) are added to the tree. We say that u is the predecessor or parent of v in the breadth-first tree.

Look at the illustration below for a better understanding.