Breadth First Search

Tags: algorithm comp-sci

Is an algorithm for [see page 7, traversing] all the nodes of a graph. It works by exploring the frontier between the discovered and undiscovered nodes, essentially placing nodes in a queue as their encountered and then popping them to search them.

def bfs(g, s):
    for v in g.vertices():
	v.color = 'white'
	v.distance = math.Infinity
	v.search_parent = None
    q = Queue()
    s.color = 'gray'
    s.distance = 0
    s.search_parent = None
    q.push(s)
    while len(q) != 0:
	u = q.dequeue()
	for v in u.edge_vertices():
	    # Skip when already visited v
	    if v.color == 'white':
		v.color = 'gray'
		v.distance = u.distance + 1
		v.search_parent = u
		q.push(v)
	u.color = 'black'

Code Snippet 1: Breadth first search implementation (see see page 9, [here]). It begins by coloring every element as white, the ones that're to be traversed are colored gray and those that we've already traversed are white. See it in action see page 10, [here].

We label the tree of nodes that we encounter while performing a breadth first search as the Breadth First Tree. All nodes where u.distance is the same are at the same level in the tree.