程序代写代做代考 algorithm 08.key

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