This page was last updated October 22, 2009

Graph Traversal

Frequently when you work with graphs you will need to perform a traversal of the graph, i.e. visit each node in the graph. Note: This is not the same as just searching the graph by iterating through the array or linked list of nodes in the graph. In order to do this you will need:

Some systematic way of traversing to ensure each node is visited.
Some way of marking nodes that have been visited to ensure that they are not visited again.

The simpliest solution is to add a boolean flag to each node, call it something like m_bVisited, set this flag in all nodes to false to start, then set each to true when a node is visited. As the traversal is conducted a list of nodes left to be visited can be kept and updated. When the list is empty the traversal is complete.


Basic Traversal Algorithm
Set a flag in all vertices to FALSE, meaning "not visited"
Pick a starting vertex
	Mark vertex V_start as visited
	Make a list of all vertices adjacent to vertex V_start
	Loop
		Select a vertex, V_i from the list. Remove the vertex from the list. Visit the vertex. Mark vertex V_i as "visited". Add to the list any vertices adjacent to V_i which have not been visited.
	Repeat until the list is empty

List Representation

How the list of nodes to be visited is implemented is important in determining how the traversal progresses. Assume we want to traverse the following graph starting at node 1. The layout of this graph was chosen to make it easier to visualize the traversals.

There are two ways to implement the list of nodes while traversing this graph. Look carefully at the state of the stack or queue at each step. In both the top/head of the list is to the left. Items pushed on to the stack are pushed from the left moving everything to the right. Items enqueued to the queue enter from the right and are dequeued from the left.

Stack

Node Visited	Action	State of Stack
1	Push 2, 3, 4	4 - 3 - 2
4	Pop 4, visit, push 8, 9	9 - 8 - 3 - 2
9	Pop 9, visit	8 - 3 - 2
8	Pop 8, visit	3 - 2
3	Pop 3, visit, push 7	7 - 2
7	Pop 7, visit	2
2	Pop 2, visit, push 5, 6	6 - 5
6	Pop 6, visit	5
5	Pop 5, visit	Empty

Order of Traversal: 1 - 4 - 9 - 8 - 3 - 7 - 2 - 6 - 5

Note that each path down from node 1 is followed as far
as possible before backing up to the last "branch" to
continue down another path. This is known as...

Depth First Traversal

Queue

Node Visited	Action	State of Queue
1	Enqueue 2, 3, 4	2 - 3 - 4
2	Dequeue 2, visit, Enqueue 5, 6	3 - 4 - 5 - 6
3	Dequeue 3, visit, Enqueue 7	4 - 5 - 6 - 7
4	Dequeue 4, visit Enqueue 8, 9	5 - 6 - 7 - 8 - 9
5	Dequeue 5, visit	6 - 7 - 8 - 9
6	Dequeue 6, visit	7 - 8 - 9
7	Dequeue 7, visit	8 - 9
8	Dequeue 8, visit	9
9	Dequeue 9, visit	Empty

Order of Traversal: 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9

Note that starting from node 1 visits all nodes one edge
away are visited first, then all nodes two edges away
are visited an so on. This is known as...