Breadth First Search Algorithm

A search algorithm that checks all neighbours of a node before going ‘deeper’. It uses a queue to store all nodes.

Pseudocode §

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"