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

1. Pseudocode

Barebones 122A Version

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

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

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

Queue based WhateverFirstSearch

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

	queue = Queue()
	put start in queue

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

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

The 122A version checks whether the adjacent vertex v is visited.

The WFS version checks if the current vertex u is new.

With time (full 122A Version)

function BFS_Search(G, start):
	DISCOVER_TIME = {}
	queue = Queue()

	for each vertex v in G:
		DISCOVER_TIME[v] = Infinity
	
	DISCOVER_TIME[start] = 0
	put start in queue

	while queue is not empty:
		u = queue.getFirst()
		for each adjacent vertex v:
			if DISCOVER_TIME[v] == Infinity:
				process(v)
				DISCOVER_TIME[v] = DISCOVER_TIME[u] + 1
				put v in queue

Old Version

process(v) is just a blackbox subroutine that you can do anything inside it.

2. Observing BFS’s Behavior

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

The changes are in red. Everything else is the same.

Barebones Version:

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

	for each vertex v in G:
		mark v as NEW

	put start in queue
	put TOKEN in queue

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

With Clock (122A Version)
Old Version

Implementation Detail

while queue has at least 1 vertex does not mean queue.size > 0.