Breadth-First Search

AlgorithmsCodingDataStructuresGraphTheory A breadth-first search is an algorithm to iterate through a graph such that one starts at a root (possibly arbitrary) and explores all neighbors before moving to any of their adjacent nodes.

Breadth first search is useful when

• We want to find a shortest path with some property
• We want to perform a tree traversal
• We can’t use recursion!

Complexity:

Time: O(|V| + |E|)
Space: O(|V|)

Iterative

from collections import deque

visited = {}
def bfs(root):
	queue = deque(root)
	visited[root] = True
	
	while(queue != []):
		n = queue.popleft()
		f(n)
			if n is not None:
				for neighbor in n.adjacent:
					if not visited[neighbor]:
						queue.append(neighbor)
						visited[neighbor] = True