1. Whatever First Search

Question. How to visit every vertex exactly once in a graph?

Def. Vertex Status

To keep track of which vertices we have seen, we use 2 $\texttt{STATUS}$ values:

• $\texttt{NEW}$: Never seen before.
• $\texttt{VISITED}$: Processed exactly once.

1.1 Pseudocode

Let T be the generic typename.

We will make up an imaginary data structure called a Bag<T>. It has 3 methods:

1. put(elem: T) puts an element in the bag.
2. getFirst() -> T returns whatever is the “first” thing in the bag and removes it.
3. isEmpty() -> bool returns whether the bag is empty or not.

Then the pseudocode for whatever first search is:

function WhateverFirstSearch(G: Graph, start: Vertex):
	for each vertex v in G:
		mark v as NEW

	bag = Bag<Vertex>()
	bag.put(start)

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

Here process(u) is just a blackbox subroutine. We can do anything inside process(u) as long as we don’t change the vertex status.

1.2 Important Variants

By changing the bag's behavior of getFirst(), we get the familiar search algorithms:

Bag is a Stack: Depth First Search

DFS is usually implemented with recursion allowing cycle detection.

See Recursive Depth First Search (122A)