Breadth First Search Algorithm

Breadth First Search is a graph search algorithm that checks all neighbours of a node before diving ‘deeper’ into a path. It uses the queue ADT to store nodes. Similar to it’s counterpart, DFS, it also relies on marking nodes to prevent searching the same node again.

Procedure §

Let $G=(V,E)$ be the graph to be labelled. Let $s$ be the start node and $t$ to be the last node.

1. Set a counter $i=0$, which measures the height of the underlying BFS tree or the distance from $s$. Mark $s=0$
2. For all unmarked vertices in $G$ that are adjacent to the $i$th-labelled node (initially just $s$):
   1. If no vertices exist and $t$ is still not labelled, terminate as there does not exist a path from $s$ to $t$
   2. Else, mark of all them with $i+1$
3. If $t$ is labelled, terminate as we have found a path. Else, increment $i$ by one and repeat step 2.

The length of the shortest path from $s$ to $t$ is $i+1$.

BFS Tree §

BFS also returns a tree , just like how DFS does. The reason the underlying structure is a tree is that because BFS marks nodes, it ensures it does not revisit a mark node (hence why it only checks for unmarked nodes).

If the graph is connected, then the BFS tree is a spanning tree. If the graph is disconnected, then BFS must be run on each connected component to produce a collection of trees, i.e. a BFS forest.

%%🖋 Edit in Excalidraw, and the dark exported image%%

If we add a back edge on the BFS tree whenever the algorithm revisits a marked node, we can recover the original graph.

Pseudocode §

Marking nodes

In the pseudocode below, there is no concrete definition of what marking means. Implementations include using node attributes, an array of nodes containing boolean values or even hash tables.

Algorithm BFS(Graph,start,end):

	queue ← Queue ADT
	output ← List
	visited ← Set ADT
	cwn ← Node ADT

	Enqueue start to queue 
	
	While queue is not Empty do: # O(|V|) 
		cwn ← Dequeued value from queue 
		If cwn not in visited then:
			Add cwn to visited
			Add cwn to output
			For edge cwn-v in outgoing edges do: #O(|E|)
				If v = end then:
					Add end to output
					Return output
				Else if v is not in visited then: #Only check unseen nodes
					Enqueue v to queue
				End if
			End do
		End if
	End do
	Return "FAIL"
	
End Algorithm #O(|V| + |E|)

Complexity §

Time Complexity: $O(|V|+|E|)$ §

$O(|V|)$ for queue + $O(|E|)$ for checking outgoing edges = $O(|V|+|E|)$

Given a complete graph, BFS would take $O\left(|V|+\frac{1}{2}|(V{|}^2-|V|)\right)$ i.e. $O(n^2)$ Worst-case it has to check the entire graph via it’s edges and store every node in the queue

Applications §

• Exploring social networks
• Searching for a specific webpage in a site
• Single-source shortest path problem
• Shortest Path Counting Algorithm
• Cycle detection

Implementation §

import networkx as nx
from queue import Queue
 
def BFS(graph: nx.Graph,start,end):
    queue = Queue()
    output = list()
    visited = set()
    queue.put(start)
    while not queue.empty():
        cwn = queue.get()
        if cwn not in visited:
            visited.add(cwn)
            output.append(cwn)
            for (u,v) in graph.edges(cwn):
                if v == end:
                    output.append(end)
                    return output
                elif v not in visited: #Only check unseen nodes
                    queue.put(v)
    return "FAIL"