# Breadth First Search (122A)

# Basics

We can implement BFS from whatever first search by using a Queue.

Barebones 122A Version

Queue based WhateverFirstSearch

function BfsSearch(G, start):
	for each vertex v in G:
		mark v as NEW

	queue = Queue()
	queue.put(start)
	mark start as VISITED

	while queue is not empty:
		u = queue.popFirst()
		process(u)
		for each adjacent vertex v:
			if v is NEW:
				mark v as VISITED
				queue.put(v)

function WfsBreadth(G, start):
	for each vertex v in G:
		mark v as NEW

	queue = Queue()
	queue.put(start)

	while queue is not empty:
		u = queue.popFirst()

		if u is NEW:
			process(u)
			mark u as VISITED
			for each adjacent vertex v:
				queue.put(v)

The 122A version checks whether the adjacent vertex v is visited. The WFS version checks if the current vertex u is new.

# Python

Github

# With time (full 122A Version)

We can also record "when" a vertex is visited. Each time we see a new vertex, we increment the "time". The discover time of a vertex starts with \infin.

function BfsSearch(G, start):
	discover_time = {}
	queue = Queue()

	for each vertex v in G:
		discover_time[v] = Infinity
	
	discover_time[start] = 0
	queue.put(start)

	while queue is not empty:
		u = queue.popFirst()
		for each adjacent vertex v:
			if discover_time[v] == Infinity:
				process(v) // arbitrary subroutine
				discover_time[v] = discover_time[u] + 1
				queue.put(v)

# Observing BFS’s Behavior / Level Order Traversal

We can observe how each "layer" of the graph is being visited by BFS by adding a special token.

The changes are highlighted. Everything else is the same.

function BfsWithToken(G, start):
	queue = Queue()

	for each vertex v in G:
		mark v as NEW

	queue.put(v)
	queue.put(TOKEN)

	while queue has at least 1 vertex:
		u = queue.popFirst()
		if u == TOKEN:
			print(TOKEN)
			queue.put(u)
		else:
			if u is NEW:
				process(u)
				mark u as VISITED
				for each adjacent vertex v:
					queue.put(v)

while queue has at least 1 vertex does not mean queue.size > 0. The special token is not a vertex.

function BfsWithToken(G, start):
	queue = Queue()

	for each vertex v in G:
		mark v as NEW

	queue.put(v)
	queue.put(TOKEN)

	while queue is not empty:
		u = queue.popFirst()
		if u == TOKEN:
			print(TOKEN)
			if queue is empty:
				break
			queue.put(u)
		else:
			if u is NEW:
				process(u)
				mark u as VISITED
				for each adjacent vertex v:
					queue.put(v)

function BfsWithToken(G, start):
	discover_time = {}
	queue = new Queue()

	for each vertex v in G:
		discover_time[v] = Infinity
	
	discover_time[start] = 0
	queue.put(v)
	queue.put(TOKEN)

	while queue has at least 1 vertex:
		u = queue.popFirst()
		if u = TOKEN:
			print(TOKEN)
			queue.put(u)
		else:
			for all edges u→v:
				if discover_time[v] == Infinity:
					process(v)
					discover_time[v] = discover_time[u] + 1
					queue.put(v)

while queue has at least 1 vertex does not mean queue.size > 0. The special token is not a vertex.

This is particularly useful if we are doing level-order traversal of a graph, because TOKEN marks the end of a level.

# Python

Github

# Examples

# EX.1

Given this graph, and we start at vertex \tt{S}

Text

Graph

Starting from \tt S, we can see that all the red nodes \tt{\red{ACG}} are 1 edge away, and the purple nodes \tt\purple{BDEFH} are 2 edges away.

# EX.2

If we start at A, then the graph will be visited in this order: A -> BCE -> D. Vertices with the same color could be visited in any order depending on the order of insertion, but the overall order is Orange → Red → Purple.

Text

Graph