08.key
http://people.eng.unimelb.edu.au/tobym
@tobycmurray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
Toby Murray
COMP90038
Algorithms and Complexity
Lecture 8: Graph Traversal
(with thanks to Harald Søndergaard)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First and
Depth-First Traversal
• Used to systematically explore all nodes of a graph
2
a
b c
d e
f
g
h
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal
3
a
b c
d e
f
g
h
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 4
a
b c
d e
f
g
h
Start with (any) node
Depth-First Traversal
Nodes visited in this order: a
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 5
a
b c
d e
f
g
h
Visit the current
node’s neighbours
depth first
(here in
alphabetical order)
Depth-First Traversal
Nodes visited in this order: a
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 6
a
b c
d e
f
g
h
Remember which
nodes we have
already visited
to avoid revisiting them
Depth-First Traversal
Visit the current
node’s neighbours
depth first
(here in
alphabetical order)
Nodes visited in this order: a b
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 7
a
b c
d e
f
g
h
Remember which
nodes we have
already visited
to avoid revisiting them
Depth-First Traversal
Nodes visited in this order: a b d
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 8
a
b c
d e
f
g
h
Back-track when
no more new
nodes to explore
Depth-First Traversal
Nodes visited in this order: a b d f
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 9
a
b c
d e
f
g
h
Depth-First Traversal
Back-track when
no more new
nodes to explore
Nodes visited in this order: a b d f e
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 10
a
b c
d e
f
g
h
Depth-First Traversal
Back-track when
no more new
nodes to explore
Nodes visited in this order: a b d f e c
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 11
a
b c
d e
f
g
h
Depth-First Traversal
Back-track when
no more new
nodes to explore
Nodes visited in this order: a b d f e c g
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 12
a
b c
d e
f
g
h
Depth-First Traversal
Nodes visited in this order: a b d f e c g h
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Stack Discipline
13
When back-tracking, we go back to the most recently-
visited node that still has unvisited neighbours
This is simulated by pushing each node onto a stack
as it is visited.
Back-tracking then corresponds to popping the stack.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 14
a
b c
d e
f
g
h
Depth-First Traversal:
Stack Discipline
(Simulated)
stack:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 15
a
b c
d e
f
g
h
Depth-First Traversal:
Stack Discipline
(Simulated)
stack:
a
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 16
a
b c
d e
f
g
h
Remember which
nodes we have
already visited
to avoid revisiting them
a b
d
Depth-First Traversal:
Stack Discipline
(Simulated)
stack:
a
b
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 17
a
b c
d e
f
g
h
Depth-First Traversal:
Stack Discipline
(Simulated)
stack:
a
b
d
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 18
a
b c
d e
f
g
h
Depth-First Traversal:
Stack Discipline
(Simulated)
stack:
a
b
d
f
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 19
a
b c
d e
f
g
h
Depth-First Traversal:
Stack Discipline
(Simulated)
stack:
a
b
d
(back-tracking)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 20
a
b c
d e
f
g
h
Depth-First Traversal:
Stack Discipline
(Simulated)
stack:
a
b
(back-tracking)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 21
a
b c
d e
f
g
h
d
Depth-First Traversal:
Stack Discipline
(Simulated)
stack:
a
b
e
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 22
a
b c
d e
f
g
h
Depth-First Traversal:
Stack Discipline
(Simulated)
stack:
a
b
e
c
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 23
a
b c
d e
f
g
h
Depth-First Traversal:
Stack Discipline
(Simulated)
stack:
a
b
e
c
back-tracking …
details omitted …
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 24
a
b c
d e
f
g
h
Depth-First Traversal:
Stack Discipline
(Simulated)
stack:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 25
a
b c
d e
f
g
h
Depth-First Traversal:
Stack Discipline
(Simulated)
stack:
g
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 26
a
b c
d e
f
g
h
Depth-First Traversal:
Stack Discipline
(Simulated)
stack:
g
h
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
27
a
b c
e
d
Call Stack
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
28
a
b c
e
d
Call Stack
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
29
a
b c
e
d
count:
0 Call Stack
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
30
a
b c
e
Call Stack
DFSEXPLORE(a)
d
count:
0
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
31
a
b c
e
Call Stack
d
count:
1
DFSEXPLORE(a)
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
32
a
b c
e
Call Stack
d
count:
1
DFSEXPLORE(b)
DFSEXPLORE(a)
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
33
a
b c
e
Call Stack
d
count:
2
DFSEXPLORE(b)
DFSEXPLORE(a)
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
34
a
b c
e
Call Stack
d
count:
2
DFSEXPLORE(b)
DFSEXPLORE(a)
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
35
a
b c
e
Call Stack
d
count:
2
DFSEXPLORE(e)
DFSEXPLORE(b)
DFSEXPLORE(a)
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
36
a
b c
e
Call Stack
d
count:
3
DFSEXPLORE(e)
DFSEXPLORE(b)
DFSEXPLORE(a)
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
37
a
b c
e
Call Stack
d
count:
3
DFSEXPLORE(e)
DFSEXPLORE(b)
DFSEXPLORE(a)
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
38
a
b c
e
Call Stack
d
count:
3
DFSEXPLORE(b)
DFSEXPLORE(a)
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
39
a
b c
e
Call Stack
d
count:
3
DFSEXPLORE(a)
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
40
a
b c
e
Call Stack
d
count:
3
DFSEXPLORE(c)
DFSEXPLORE(a)
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
41
a
b c
e
Call Stack
d
count:
4
DFSEXPLORE(c)
DFSEXPLORE(a)
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
42
a
b c
e
Call Stack
d
count:
4
DFSEXPLORE(c)
DFSEXPLORE(a)
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
43
a
b c
e
Call Stack
d
count:
4
DFSEXPLORE(a)
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
44
a
b c
e
Call Stack
d
count:
4
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
45
a
b c
e
Call Stack
d
count:
4
DFS(⟨V,E⟩)
DFSEXPLORE(d)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
46
a
b c
e
Call Stack
d
count:
5
DFS(⟨V,E⟩)
DFSEXPLORE(d)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
47
a
b c
e
Call Stack
d
count:
5
DFS(⟨V,E⟩)
DFSEXPLORE(d)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
48
a
b c
e
Call Stack
d
count:
5
DFS(⟨V,E⟩)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Traversal:
Recursive Implementation
49
a
b c
e
Call Stack
d
count:
5
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Search:
Recursive Algorithm Notes
• Works both for directed and undirected graphs.
• The “marking” of nodes is usually done by maintaining a separate
array, mark, indexed by V .
• For example, when we wrote “mark v with count”, that would be
implemented as “mark[v] := count”.
• How to find the nodes adjacent to v depends on the graph
representation used.
• Using an adjacency matrix adj, we need to consider adj[v,w]
for each w in V . Here the complexity of graph traversal is Θ(|V|2).
• Using adjacency lists, for each v , we traverse the list adj[v].
In this case, the complexity of traversal is Θ(|V| + |E|).
50
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Applications of Depth-First
Search (DFS)
• Easy to adapt DFS
to decide if a graph
is connected.
• How?
51
a
b c
e
d
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Search:
Node Orderings
• We can order nodes either by the order in which
they get pushed onto the stack, or by the order in
which they are popped from the stack
52
Levitin’s compact stack notation
The first subscripts give the order in which
nodes are pushed, the second the order in
which they are popped off the stack.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First Search Forest
53
DFS can be depicted by the
resulting DFS Forest
(DFS Tree for a connected graph)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
54
a
b c
d e
f
g
h
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
55
a
b c
d e
f
g
h
Start with (any) node
Nodes visited in this order: a
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
56
a
b c
d e
f
g
h
Visit all of its neighbours
Nodes visited in this order: a
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
57
a
b c
d e
f
g
h
Visit all of its neighbours
Nodes visited in this order: a b
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
58
a
b c
d e
f
g
h
Visit all of its neighbours
Nodes visited in this order: a b c
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
59
a
b c
d e
f
g
h
Then visit all of their
neighbours, and so on
Nodes visited in this order: a b cd
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
60
a
b c
d e
f
g
h
Then visit all of their
neighbours, and so on
Nodes visited in this order: a b cd e
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
61
a
b c
d e
f
g
h
Then visit all of their
neighbours, and so on
Nodes visited in this order: a b cd e f
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
62
a
b c
d e
f
g
h
Then visit all of their
neighbours, and so on
Nodes visited in this order: a b cd e f g
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Traversal
63
a
b c
d e
f
g
h
Then visit all of their
neighbours, and so on
Nodes visited in this order: a b cd e f g h
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First vs
Breadth-First Search
64
Typical Depth-First Search
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Depth-First vs
Breadth-First Search
65
Typical Breadth-First Search
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search:
Queue Discipline
66
a
b c
d e
f
g
h
Traversal
Queue:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search:
Queue Discipline
67
a
b c
d e
f
g
h
Traversal
Queue:
a
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 68
a
b c
d e
f
g
h
Traversal
Queue:
Breadth-First Search:
Queue Discipline
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 69
a
b c
d e
f
g
h
Traversal
Queue:
b
c
Breadth-First Search:
Queue Discipline
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 70
a
b c
d e
f
g
h
Traversal
Queue:
c
Breadth-First Search:
Queue Discipline
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 71
a
b c
d e
f
g
h
Traversal
Queue:
c
d
Breadth-First Search:
Queue Discipline
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 72
a
b c
d e
f
g
h
Traversal
Queue:
d
Breadth-First Search:
Queue Discipline
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 73
a
b c
d e
f
g
h
Traversal
Queue:
d
e
Breadth-First Search:
Queue Discipline
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 74
a
b c
d e
f
g
h
Traversal
Queue:
e
Breadth-First Search:
Queue Discipline
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 75
a
b c
d e
f
g
h
Traversal
Queue:
e
f
Breadth-First Search:
Queue Discipline
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 76
a
b c
d e
f
g
h
Traversal
Queue:
f
Breadth-First Search:
Queue Discipline
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 77
a
b c
d e
f
g
h
Traversal
Queue:
Breadth-First Search:
Queue Discipline
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 78
a
b c
d e
f
g
h
Traversal
Queue:
Breadth-First Search:
Queue Discipline
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 79
a
b c
d e
f
g
h
Traversal
Queue:
g
Breadth-First Search:
Queue Discipline
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 80
a
b c
d e
f
g
h
Traversal
Queue:
Breadth-First Search:
Queue Discipline
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 81
a
b c
d e
f
g
h
Traversal
Queue:
h
Breadth-First Search:
Queue Discipline
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 82
a
b c
d e
f
g
h
Traversal
Queue:
Breadth-First Search:
Queue Discipline
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Breadth-First Search
Algorithm
83
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
BFS Algorithm Notes
• BFS has the same complexity as DFS.
• Again, the same algorithm works for directed
graphs as well.
• Certain problems are most easily solved by
adapting BFS.
• For example, given a graph and two nodes, a and
b in the graph, how would you find the length of the
shortest path from a to b?
84
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
In general, we may get a
BFS Forest
BFS Tree for this
connected graph:
Breadth-First Search Forest
85
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting
• We mentioned scheduling problems and their representation by
directed graphs.
• Assume a directed edge from a to b means that task a must be
completed before b can be started.
• The graph must be a dag; otherwise the problem cannot be
solved.
• Assume the tasks are carried out by a single person, unable to
multi-task.
• Then we should try to linearize the graph, that is, order the nodes
as a sequence v1,v2,…,vn such that for each edge (vi,vj) ∈ E, we
have vi comes before vj in the sequence (that is, vi is scheduled to
happen before vj).
86
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting
Example
87
There are 4 ways to linearise the following graph
Here is one:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting
Algorithm 1
• We can solve the top-sort problem with depth-first search:
1. Perform DFS and note the order in which nodes are
popped off the stack.
2. List the nodes in the reverse of that order.
• This works because of the stack discipline.
• If (u,v) is an edge then it is possible (given some way of
deciding ties) to arrive at a DFS stack with u sitting below
v.
• Taking the “reverse popping order” ensures that u is listed
before v.
88
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting
Example Again
89
Using the DFS method and resolving ties by using
alphabetical order, the graph gives rise to the traversal
stack shown on the right (the popping order shown in red):
Taking the nodes in reverse popping order yields
b, d, a, c, f , e.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting
Algorithm 2
90
• An alternative method would be to repeatedly
select a random source in the graph (that is, a
node with no incoming edges), list it, and remove it
from the graph (including removing its outgoing
edges).
• This is a very natural approach, but it has the
drawback that we repeatedly need to scan the
graph for a source.
• However, it exemplifies the general principle of
decrease-and-conquer.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting
Example Again
91
Using the source removal method (and resolving ties
alphabetically):
Topological sorted order:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting
Example Again
92
Using the source removal method (and resolving ties
alphabetically):
Topological sorted order:
b
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting
Example Again
93
Using the source removal method (and resolving ties
alphabetically):
Topological sorted order:
b, a
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting
Example Again
94
Using the source removal method (and resolving ties
alphabetically):
Topological sorted order:
b, a, d
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting
Example Again
95
Using the source removal method (and resolving ties
alphabetically):
Topological sorted order:
b, a, d, c
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting
Example Again
96
Using the source removal method (and resolving ties
alphabetically):
Topological sorted order:
b, a, d, c, e
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Topological Sorting
Example Again
97
Using the source removal method (and resolving ties
alphabetically):
Topological sorted order:
b, a, d, c, e, f
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Next time
• So next we turn our attention to the very useful
“decrease and conquer” principle
(Levitin Chapter 4).
98