Topic 2.

Graph traversal algorithms

Objectives
• Be able to trace depth-first and breadth-first
algorithms
• Describe typical applications of each
Graph traversal algorithms
Unit 12 Algorithms

A list representation of a graph

• Draw the graph represented by the following list:

A [B, C]
B [A, D, E]
C [A, F, G]
D [B, E]
E [B, D]
F [C,G]
G [C,F,H,I]
H [G,I]
I [G,H,X]
X [I]
Graph traversal algorithms
Unit 12 Algorithms

Answer
• Terminology associated with graphs

B and C are adjacent nodes

A [B, C] or neighbours of A
B [A, D, E]
C [A, F, G]
D [B, E]
E [B, D]
F [C,G]
G [C,F,H,I] Node or
H [G,I]
vertex
I [G,H,X] Undirected edge
X [I]
Graph traversal algorithms
Unit 12 Algorithms

Traversing a graph
• There are two ways of traversing a graph:
• Depth-first
• Breadth-first

• With depth-first, you go as far as you can down a

path before backtracking and going down the next
path
• With breadth-first, you explore all the neighbours of
the current vertex, then the neighbours of each of
those vertices and so on
Graph traversal algorithms
Unit 12 Algorithms

A depth-first traversal
• We will traverse the graph represented by the
following dictionary data structure
GRAPH = { "A":["B","D","E"], "B":["A","C","D"], "C":["B","G"],
"D":["A","B","E","F"], "E":["A","D"] , "F":["D"], "G":
["C"]}
Graph traversal algorithms
Unit 12 Algorithms

Depth-first traversal
• The algorithm uses a stack to keep track of the last
node visited, and a list to hold the names of nodes
that have been visited
• Start with an empty stack and an empty list
Graph traversal algorithms
Unit 12 Algorithms

Depth-first traversal
• Visit A, and add it to the visited list
• Colour it green to show it has been visited
Graph traversal algorithms
Unit 12 Algorithms

Depth-first traversal
• Push A onto the stack to keep track of where we
have come from and visit A’s first neighbour, B. Add
it to the visited list
• Colour it to show it has been visited
Graph traversal algorithms
Unit 12 Algorithms

Depth-first traversal
• Push B onto the stack and from B, visit the next
unvisited node, C
• Add it to the visited list
• Colour it to show it has been visited
Graph traversal algorithms
Unit 12 Algorithms

Depth-first traversal
• Push C onto the stack and from C, visit the next
unvisited node, G
• Add it to the visited list. Colour G to show it has been
visited
Graph traversal algorithms
Unit 12 Algorithms

Depth-first traversal
• At G, there are no unvisited nodes so we backtrack
• Pop the previous node C off the stack and return to
C

C
Graph traversal algorithms
Unit 12 Algorithms

Depth-first traversal
• At C, all adjacent nodes have been visited, so
backtrack again
• Pop B off the stack and return to B

B
Graph traversal algorithms
Unit 12 Algorithms

Depth-first traversal
• Push B back onto the stack to keep track of where
we have come from and visit D
• Add it to the visited list
• Colour D to show it has been visited
Graph traversal algorithms
Unit 12 Algorithms

Depth-first traversal
• Push D back onto the stack and visit E
• Add E to the visited list
• Colour E to show it has been visited
Graph traversal algorithms
Unit 12 Algorithms

Depth-first traversal
• From E, A and D have already been visited so pop D
off the stack and return to D

D
Graph traversal algorithms
Unit 12 Algorithms

Depth-first traversal
• Push D back onto the stack and visit F
• Add it to the visited list
• Colour it to show it has been visited
Graph traversal algorithms
Unit 12 Algorithms

Depth-first traversal
• At F, there are no unvisited nodes so we pop D

D
Graph traversal algorithms
Unit 12 Algorithms

Depth-first traversal
• B is popped

B
Graph traversal algorithms
Unit 12 Algorithms

Depth-first traversal
• A is popped
• The stack is now empty which means every node
has been visited and the algorithm has completed

A
Graph traversal algorithms
Unit 12 Algorithms

Algorithm for depth-first

function dfs(graph, currentVertex, visited)
append currentVertex to list of visited nodes
for vertex in graph[currentVertex]
if vertex not in visited then
dfs(graph, vertex, visited)
endif
next vertex
return visited
endfunction
• This subroutine returns a list of the nodes in the
order that they have been visited
Graph traversal algorithms
Unit 12 Algorithms

Applications of depth-first
traversal
• Job-scheduling, where some jobs have to be
completed before others can begin
• Finding a path between two vertices
• Solving puzzles such as navigating a maze
Graph traversal algorithms
Unit 12 Algorithms

Graph representing a maze

• A maze can be represented by a graph; dead ends
are shown as a bar

• Nodes represent the entrance to or exit from the maze,

points at which more than one path can be taken, and dead
ends
Graph traversal algorithms
Unit 12 Algorithms

Graph representing a maze

• Alternatively, you can draw the graph without
showing dead ends:
Graph traversal algorithms
Unit 12 Algorithms

Worksheet 5
• Try Task 1 on the worksheet
Graph traversal algorithms
Unit 12 Algorithms

Breadth-first traversal
• With a breadth first traversal, all the nodes adjacent
to A are visited before moving to B
• The process is repeated for each node at this ‘level’,
before moving to the next level
• Instead of a stack, a queue is used to keep track of
nodes that we still have to visit
• Nodes are coloured pale green when queued and dark green
when dequeued and added to the list of nodes that have been
visited
Graph traversal algorithms
Unit 12 Algorithms

Breadth-first traversal
• Append A to the empty queue at the start of the
routine
• This will be the first visited node
Graph traversal algorithms
Unit 12 Algorithms

Breadth-first traversal
• Dequeue A and mark it by colouring it dark green
• Add A to the visited list
Graph traversal algorithms
Unit 12 Algorithms

Breadth-first traversal
• Queue each of A’s adjacent nodes B, D and E in turn
• Colour each node pale green to show it has been
queued
Graph traversal algorithms
Unit 12 Algorithms

Breadth-first traversal
• We’ve now finished with A, so dequeue the first item
in the queue, which is B
• Mark it by colouring it dark green and add it to the
visited list
Graph traversal algorithms
Unit 12 Algorithms

Breadth-first traversal
• Queue B’s remaining neighbour C
• Colour it pale green to show it has been queued
Graph traversal algorithms
Unit 12 Algorithms

Breadth-first traversal
• B’s neighbours are all coloured, so dequeue the first
item in the queue, which is D
• Mark it by colouring it dark green and add it to the
visited list
Graph traversal algorithms
Unit 12 Algorithms

Breadth-first traversal
• D’s adjacent node E has already been queued and
coloured. Add D’s adjacent node F to the queue
• Colour F pale green to show it has been queued
Graph traversal algorithms
Unit 12 Algorithms

Breadth-first traversal
• Dequeue the first item, E
• Mark E by colouring it dark green and add it to the
visited list
Graph traversal algorithms
Unit 12 Algorithms

Breadth-first traversal
• E’s neighbours are all coloured, so dequeue the next
item, C
• Mark C by colouring it dark green and add it to the
visited list
Graph traversal algorithms
Unit 12 Algorithms

Breadth-first traversal
• Add C’s adjacent node G to the queue
• Colour G pale green to show it has been queued
Graph traversal algorithms
Unit 12 Algorithms

Breadth-first traversal
• C’s neighbours are all coloured now, so dequeue F
• Mark F by colouring it dark green
• Add it to the visited list
Graph traversal algorithms
Unit 12 Algorithms

Breadth-first traversal
• Finally, dequeue G, mark it by colouring it dark green
and add it to the visited list
• The queue is now empty and all the nodes have
been visited
Graph traversal algorithms
Unit 12 Algorithms

Worksheet 5
• Try Task 2 on the worksheet
Graph traversal algorithms
Unit 12 Algorithms

Applications of breadth-first
traversal
• Finding the shortest path between two points
• A Web crawler uses a breadth-first search to analyse
sites that you can reach by following links randomly
• Facebook uses a breadth-first search to find all the
friends of a given individual
Graph traversal algorithms
Unit 12 Algorithms

Complexity of DFS and BFS

• A depth-first search and a breadth-first search both
visit every vertex and explore every edge
• In a sparse graph, the number of operations is therefore n + e
where n = number of vertices and e= number of edges
• This is effectively O(n)
• In a graph which has the maximum possible edges, the
adjacency matrix is full so there are n edges and n2 edges,
giving vn2 + n
• This is essentially O(n2) since only the dominant term is
relevant
Graph traversal algorithms
Unit 12 Algorithms

Depth-first tree traversal

• A tree is a special case of a graph, having no cycles

• What order are the nodes visited in using a pre-order

traversal?
• What order are they visited in using a depth-first traversal?
Graph traversal algorithms
Unit 12 Algorithms

Pre-order and depth-first tree

traversals

• Both the traversals visit the nodes in the order:

Monkey, Giraffe, Buffalo, Baboon, Cheetah, Hippo,
Jackal, Topi, Ostrich, Rhino, Zebra
Graph traversal algorithms
Unit 12 Algorithms

Breadth-first tree traversal

• Breadth-first, nodes are visited in the order
M, H, N, D, L, P, A, J, O, T
• What order are they visited in using a post-order
traversal?
Graph traversal algorithms
Unit 12 Algorithms

Post-order tree traversal

• Breadth-first, nodes are visited in the order
M, H, N, D, L, P, A, J, O, T
• In a post-order traversal,
A, D, J, L, H, O, T, P, N, M
Graph traversal algorithms
Unit 12 Algorithms

Worksheet 5
• Do Task 3 on the worksheet
Graph traversal algorithms
Unit 12 Algorithms

Plenary
• There are two ways of searching a graph
• Each has its own particular uses
• Each uses a different supporting data structure in
the traversal algorithm
• What are the data structures used in each case?