The Only Graph Traversal Algorithm

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

Whatever First Search

Def. Vertex Status

To keep track of which vertices we have seen, we use 2 STATUS values:

NEW: Never seen before.
SEEN: Processed exactly once.

Let T be the generic type name. We will make up an imaginary data structure called a Bag<T>. It has 3 methods:

put(element: T) puts an element in the bag.
popFirst() -> T returns whatever is the "first" thing in the bag and removes it.
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.popFirst()
		if u is NEW:
			process(u) 
			mark u as SEEN
			for each v adjacent to 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.

Important Variants

By changing the bag's behavior of popFirst() and put(element), we get the familiar search algorithms:

Stack

Depth First Search. DFS is usually implemented with recursion allowing cycle detection.

put(element) appends to the end
popFirst() pops from the end

Queue

Breadth First Search

put(element) appends to the end
popFirst() pops from the front

Priority Queue

Best First Search

put(element) appends with a priority value in O(\log n) time
popFirst() pops the element with highest priority in O(\log n) time.

Implementation Tip

In python, we can easily swap between DFS and BFS by using collections.deque.

<deque>.popleft() gives us BFS
<deque>.pop() gives us DFS

C++ also has std::deque<T>

For priority queue we could use heapq on a regular list [].

Use heappush and heappop to append and pop from the priority queue. See its use in Dijkstra's Algorithm.

We can represent NEW and SEEN with a set

function WhateverFirstSearch(G: Graph, start: Vertex):
	bag = Bag<Vertex>()
	bag.put(start)

	seen_vertices = Set<Vertex>()

	while bag is not empty:
		u = bag.popFirst()
		if not seen_vertices.has(u):
			process(u) 
			seen_vertices.add(u)
			for each v adjacent to u:
				bag.put(v)

Python

The WhateverFirstSearch_Connected function implements this. Github

Assumption

This version of Whatever First Search assumes that the start can actually reach every other vertex in the graph. This works if we know the graph is connected.

To handle disconnected graphs we need to make the following modifications.

Whatever First Search–All

For each vertex in G, if we’ve never visited this vertex before, visit everything that we can reach from this vertex.

We will make a small wrapper.

// main routine
function WhateverFirstSearch(G: Graph):
	for each vertex v in G:
		mark v as NEW
	for each vertex v in G:
		if v is NEW:
			WhateverFirstVisit(G, v)
			
function WhateverFirstVisit(G: Graph, start: Vertex):
	bag = Bag<Vertex>()
	bag.put(start)

	while bag is not empty:
		u = bag.popFirst()
		if u is not SEEN:
			process(u)
			mark u as SEEN
			for each v adjacent to u:
				bag.put(v)

Changing the bag's behavior on popFirst() will result in the same variants, but now they can handle disconnected graphs.

Python

The WhateverFirstSearch_All function implements this. Github