Graph - Breadth First Search OR BFS Traversal

The Idea

Compared to depth first search (DFS), this traversal method prioritizes exploring closer neighbours first. It ensures that all nodes at a similar distance from the starting point are visited before moving on to nodes further away.

This creates a wave-like expansion outward, visiting all nodes at a specific distance before progressing to the next layer.

Examples

Example 1

We can thing of breadth first search as a “wave” walk through the graph. In other words we go level by level, as shown on the picture below.

Example 2

For this very specific graph on the picture we can see how breadth first search walks through the graph level by level!

Consider the graph

Let s be the starting vertex. Layer 0 is node s, then a and b are layer 1. So, when layer 0 is processed, we add layer 1 to queue. Layer n+1 gets added to the queue when we process layer n.

Example 3

Here is an example of such a traversal.

It means that none of the Frontier n vertices can be visited until all the vertices in frontier n-1 is visited.

Algorithm

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

1. Visited OR explored
2. Not Visited OR Unexplored

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

The algorithm works as follows:

1. Initialization: Choose any vertex in the graph as the starting point (s). Mark s as explored.
2. Exploration: Process s according to the specific problem being solved (e.g., collect data, perform calculations).
3. Neighbour Processing: Identify all unvisited neighbours connected to s.
4. Iteration:  For each unvisited neighbor, mark it as explored, process it, and then repeat steps 2 and 3 until all reachable nodes are explored.

Pseudo Code

BFS(graph G, vertex s)
[all nodes initially unexplored]
-mark s as explored
let Q = queue data structure
Q.enqueue(s)
while (Q not empty)
     //remove the first node of Q, call it v
     v = Q.dequeue()
    for each edge (v, w):
         if w is unexplored
              mark w as explored
              add w to Q (at the end)

Code

Java

 private List bfs(List<List> graph) {
 	List visitedList = new ArrayList();
 	Queue tempQueue = new ArrayDeque();
 	tempQueue.add(1);
 	visitedList.add(1);
 	Integer poll = null;
 	while (!tempQueue.isEmpty()) {
 		poll = tempQueue.poll();
 		List adjListForPoll = graph.get(poll - 1);
 		for (Integer vertex: adjListForPoll) {
 			if (!visitedList.contains(vertex)) {
 				visitedList.add(vertex);
 				tempQueue.offer(vertex);
 			}
 		}
 	}

 	return visitedList;
 }

Time Complexity

Adjacency list implementation of graph - O(|V|+|E|) OR O(n+m) where |V| and |E| is number of vertices and edges for adjacency list representation of graph. The first loop runs till the Queue has some value. It will be a max of V times. The inner loop runs for K times where K is the size of the adjacency list of the vertex (or the number of edges connected to the vertex under process).

Running time for adjacency matrix - O(|V|^2) OR O(n^2)

where V - number of vertices and E number of edges which can be reached from the starting vertex. Also this is time complexity for adjacency list implementation.

BFS Dry run Example

Let’s see how the Breadth First Search algorithm works with an example. We use an undirected graph with 5 vertices.

Here is the video:

Applications of Breadth First Traversal

• Graph Traversal: Explores connected nodes level-by-level.
• Shortest Paths (unweighted): Finds the quickest route between two points.
• Data Structures: Serializes/deserializes tree data structure.
• Garbage collection: It can also be used in garbage collection in modern programming languages, which is done by traversing an object graph.
• Memory Management: Aids garbage collection in modern languages.
• Graph Analysis: Checks for bipartite graphs and cycles.
• Path finding algorithms
• In Ford-Fulkerson algorithm to find maximum flow in a network
• Check if path exists between 2 nodes in Graph
• In minimum spanning tree
• Cycle detection in an undirected graph

Real-World Examples:

• GPS navigation

• Tournament Scheduling: How can we conduct matches between teams in a Cricket tournament such that all group 1 teams can play match with all other teams in remaining groups?Ensures balanced play between groups.

• Travel Route Planning: Optimizes itineraries for minimal cost.

• Social Network Recommendations: How sites like Facebook and LinkedIn suggest relevant connections

• Search Engines: Contributes to web page indexing.

• Web Crawling: Systematically explores and organizes web pages.

• This can also be used in finding out shortest paths between two nodes.

• Another application can be serializing and de-serializing a tree data structure.