# CS代考 COMP90038 – cscodehelp代写

COMP90038
Algorithms and Complexity
Lecture 8: Graph Traversal (with thanks to Harald Søndergaard)

DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray

Used to systematically explore all nodes of a graph a

bc
de
g
h
2
f

Depth-First Traversal
a
bc
de
g
h
3
f

Depth-First Traversal Nodes visited in this order: a
a
bc
de
g
h
4
f

Depth-First Traversal Nodes visited in this order: a
Visit the current node’s neighbours depth first (here in alphabetical order)
a
bc
de
g
h
f

Depth-First Traversal Nodes visited in this order:
Visit the current node’s neighbours depth first (here in alphabetical order)
a b
bc
a
g
h
de
f
Remember which nodes we have already visited
to avoid revisiting them

Depth-First Traversal
Nodes visited in this order: a b d
a
bc
g
h
de
7
f
Remember which nodes we have already visited
to avoid revisiting them

Depth-First Traversal Nodes visited in this order:
a b d f
bc
de
Back-track when no more new nodes to explore
a
g
h
8
f

Depth-First Traversal Nodes visited in this order:
a b d f e
bc
de
Back-track when no more new nodes to explore
a
g
h
9
f

Depth-First Traversal Nodes visited in this order:
a b d f e c
bc
de
Back-track when no more new nodes to explore
a
g
h
10
f

Depth-First Traversal Nodes visited in this order:
a b d f e c g
bc
de
Back-track when no more new nodes to explore
a
g
h
11
f

Depth-First Traversal
Nodes visited in this order: a b d f e c g h
a
bc
de
g
h
f

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.

Depth-First Traversal: Stack Discipline
(Simulated) stack:
a
bc
de
g
h
f

Depth-First Traversal: Stack Discipline
(Simulated) stack:
a
a
bc
de
g
h
f

Depth-First Traversal: Stack Discipline
ab
a
bc
g
h
(Simulated) stack:
b
a
d e
f
Remember which nodes we have already visited
to avoid revisiting them

Depth-First Traversal: Stack Discipline
(Simulated) stack:
d b a
a
bc
de
g
h
f

Depth-First Traversal: Stack Discipline
(Simulated) stack:
f d b a
a
bc
de
g
h
f

Depth-First Traversal: Stack Discipline
(back-tracking)
a
bc
de
g
h
(Simulated) stack:
d b a
f

Depth-First Traversal: Stack Discipline
(back-tracking)
a
bc
de
g
h
(Simulated) stack:
b
a
f

Depth-First Traversal: Stack Discipline
(Simulated) stack:
e
b
a
a
bc
d e
g
h
f

Depth-First Traversal: Stack Discipline
(Simulated) stack:
c e
b
a
a
bc
de
g
h
f

Depth-First Traversal: Stack Discipline
(Simulated) stack:
c e
b
a
a
bc
de
back-tracking … details omitted …
g
h
f

Depth-First Traversal: Stack Discipline
(Simulated) stack:
a
bc
de
g
h
f

Depth-First Traversal: Stack Discipline
(Simulated) stack:
g
a
bc
de
g
h
f

Depth-First Traversal: Stack Discipline
(Simulated) stack:
h g
a
bc
de
g
h
f

Depth-First Traversal: Recursive Implementation
bc e
Call Stack

Depth-First Traversal: Recursive Implementation
bc e
DFS(⟨V,E⟩) Call Stack

Depth-First Traversal: Recursive Implementation
bc e
count: 0
DFS(⟨V,E⟩) Call Stack

Depth-First Traversal: Recursive Implementation
bc e
DFSEXPLORE(a) count: DFS(⟨V,E⟩)
0
Call Stack

Depth-First Traversal: Recursive Implementation
bc e
DFSEXPLORE(a) count: DFS(⟨V,E⟩)
1
Call Stack

Depth-First Traversal: Recursive Implementation
bc e
count: 1
DFSEXPLORE(b) DFSEXPLORE(a) DFS(⟨V,E⟩) Call Stack

Depth-First Traversal: Recursive Implementation
bc e
count: 2
DFSEXPLORE(b) DFSEXPLORE(a) DFS(⟨V,E⟩) Call Stack

Depth-First Traversal: Recursive Implementation
bc e
count: 2
DFSEXPLORE(b) DFSEXPLORE(a) DFS(⟨V,E⟩) Call Stack

Depth-First Traversal: Recursive Implementation
bc e
count: 2
DFSEXPLORE(e) DFSEXPLORE(b)
DFSEXPLORE(a) DFS(⟨V,E⟩) Call Stack

Depth-First Traversal: Recursive Implementation
bc e
count: 3
DFSEXPLORE(e) DFSEXPLORE(b)
DFSEXPLORE(a) DFS(⟨V,E⟩) Call Stack

Depth-First Traversal: Recursive Implementation
bc e
count: 3
DFSEXPLORE(e) DFSEXPLORE(b)
DFSEXPLORE(a) DFS(⟨V,E⟩) Call Stack

Depth-First Traversal: Recursive Implementation
bc e
count: 3
DFSEXPLORE(b) DFSEXPLORE(a) DFS(⟨V,E⟩) Call Stack

Depth-First Traversal: Recursive Implementation
bc e
DFSEXPLORE(a) count: DFS(⟨V,E⟩)
3
Call Stack

Depth-First Traversal: Recursive Implementation
bc e
count: 3
DFSEXPLORE(c) DFSEXPLORE(a)
DFS(⟨V,E⟩) Call Stack

Depth-First Traversal: Recursive Implementation
bc e
count: 4
DFSEXPLORE(c) DFSEXPLORE(a)
DFS(⟨V,E⟩) Call Stack

Depth-First Traversal: Recursive Implementation
bc e
count: 4
DFSEXPLORE(c) DFSEXPLORE(a)
DFS(⟨V,E⟩) Call Stack

Depth-First Traversal: Recursive Implementation
bc e
DFSEXPLORE(a) count: DFS(⟨V,E⟩)
4
Call Stack

Depth-First Traversal: Recursive Implementation
bc e
count: 4
DFS(⟨V,E⟩) Call Stack

Depth-First Traversal: Recursive Implementation
bc e
DFSEXPLORE(d) count: DFS(⟨V,E⟩)
4
Call Stack

Depth-First Traversal: Recursive Implementation
bc e
DFSEXPLORE(d) count: DFS(⟨V,E⟩)
5
Call Stack

Depth-First Traversal: Recursive Implementation
bc e
DFSEXPLORE(d) count: DFS(⟨V,E⟩)
5
Call Stack

Depth-First Traversal: Recursive Implementation
bc e
count: 5
DFS(⟨V,E⟩) Call Stack

Depth-First Traversal: Recursive Implementation
bc e
count: 5
Call Stack

50
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.

for each w in V . Here the complexity of graph traversal is Θ(|V|2).

In this case, the complexity of traversal is Θ(|V| + |E|).

Applications of Depth-First Search (DFS)
Easy to adapt DFS to decide if a graph is connected.
How?
bc
e

51

Depth-First Search: Node Orderings
We can order nodes either by the order in which which they are popped from the stack

they get pushed onto the stack, or by the order in
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.
52

Depth-First Search Forest
DFS can be depicted by the resulting DFS Forest
(DFS Tree for a connected graph)

a
bc
de
g
h
f

Nodes visited in this order: a
a
bc
de
g
h
f

Nodes visited in this order: a
Visit all of its neighbours
a
bc
de
g
h
f

Nodes visited in this order: a b
Visit all of its neighbours
a
bc
de
g
h
f

Nodes visited in this order: a b c
Visit all of its neighbours
a
bc
de
g
h
f

Nodes visited in this order: a b c d Then visit all of their
neighbours, and so on a bc
de
f
g
h

Nodes visited in this order: a b c d e Then visit all of their
neighbours, and so on a bc
de
f
g
h

Nodes visited in this order: a b c d e f Then visit all of their
neighbours, and so on a bc
de
f
g
h

Nodes visited in this order: a b cd e f g Then visit all of their
neighbours, and so on a bc
de
f
g
h

Nodes visited in this order: a b c d e f g h Then visit all of their
neighbours, and so on a bc
de
f
g
h

Typical Depth-First Search

Traversal Queue:
a
bc
de
g
h
f

Traversal Queue:
a
a
bc
de
g
h
f

Traversal Queue:
a
bc
de
g
h
f

Traversal Queue:
b c
a
bc
de
g
h
f

Traversal Queue:
c
a
bc
de
g
h
f

Traversal Queue:
c d
a
bc
de
g
h
f

Traversal Queue:
d
a
bc
de
g
h
f

Traversal Queue:
d e
a
bc
de
g
h
f

Traversal Queue:
e
a
bc
de
g
h
f

Traversal Queue:
ef
a
bc
de
g
h
f

Traversal Queue:
f
a
bc
de
g
h
f

Traversal Queue:
a
bc
de
g
h
f

Traversal Queue:
a
bc
de
g
h
f

Traversal Queue:
g
a
bc
de
g
h
f

Traversal Queue:
a
bc
de
g
h
f

Traversal Queue:
h
a
bc
de
g
h
f

Traversal Queue:
a
bc
de
g
h
f

84
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

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?

BFS Tree for this connected graph:
In general, we may get a BFS Forest

86
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 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).

Topological Sorting Example
There are 4 ways to linearise the following graph
Here is one:

88
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.

Topological Sorting Example Again
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.

90
Topological Sorting Algorithm 2
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.

Topological Sorting Example Again
Using the source removal method (and resolving ties alphabetically):
Topological sorted order:

Topological Sorting Example Again
Using the source removal method (and resolving ties alphabetically):
Topological sorted order: b

Topological Sorting Example Again
Using the source removal method (and resolving ties alphabetically):
Topological sorted order: b, a

Topological Sorting Example Again
Using the source removal method (and resolving ties alphabetically):
Topological sorted order: b, a, d

Topological Sorting Example Again
Using the source removal method (and resolving ties alphabetically):
Topological sorted order: b, a, d, c

Topological Sorting Example Again
Using the source removal method (and resolving ties alphabetically):
Topological sorted order: b, a, d, c, e