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.

Process §

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
• Shortest Path between 2 nodes
• 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"