Microsoft Word - 문서2
Do not modify Graph.java
Task:
1. Implement topologicalOrdering1() in the starter code (DFS.java). This is the DFSbased algorith
m for finding the topological ordering of a directed acyclic graph. Do not modify Graph.java.
Use it from package idsa.
Student’s questions regarding assignment & answe
l Input graph may not be a DAG. Your program should detect and output appropriate message.
Practice Task (Optional) -> You don’t have to do it!
2. Implement topologicalOrdering2(g) in the starter code. In this algorithm, we identify a node
with no incoming edges, and remove it and all its edges. Repeat this until the graph is em
pty.
3. Implement connectedComponents() in the starter code. In this algorithm, use DFS to find th
e number of connected components of a given undirected graph. Each node gets a cno. All
nodes in the same connected component receive the same cno.
PowerPoint Presentation
DFS
Sridhar Alaga
CS 6301 IDSA
DFS in a directed Graph
2
Use stack for DFS
dfs(v){
if v is unmarked
mark v
for each (v, w) in G do
dfs(w)
}
wfs(s){
put s into bag
while bag not empty
take v from bag
if v is unmarked
mark v
for each (v, w) in G do
put w in bag
}
DFS
3
Wrapper method to visit all nodes
dfs(v){
mark v
pre(v)
for each (v, w) in G do
if w is unmarked
w.parent = v
dfs(w)
post(v)
}
dfsAll(G){
initialize(G)
for each v in G do
unmark v
for each v in G do
if v is unmarked
dfs(v)
}
Preorder and postorder traversal of DFS Forest
4
dfs(v){
mark v
pre(v)
for each (v, w) in G do
if v is unmarked
w.parent = v
dfs(w)
post(v)
}
dfsAll(G){
initialize(G)
for each v in G do
unmark v
for each v in G d0
if v is unmarked
dfs(v)
}
initialize(G)
clock = 0
pre(v)
clock++
v.start = clock
post(v)
clock++
v.finish = clock
Record when a node entered and left stack
Recursion Stack – Time diagram
5
Stack – Time diagram
6
Stack – Time diagram
7
Stack – Time diagram
8
Stack – Time diagram
9
Stack – Time diagram
10
Stack – Time diagram
11
Stack – Time diagram
12
Stack – Time diagram
13
Stack – Time diagram
14
Stack – Time diagram
15
Stack – Time diagram
16
Stack – Time diagram
17
18
Preorde
postorde
Preorder and postorder traversal of DFS Forest
pre(v)
startList.add(v)
post(v)
finishList.add(v)
Classifying Vertices
• v is new if DFS(v) is not called
• clock < v.start
• v is active if DFS(v) is called but not returned
• v.start <= clock < v.finish
• v is finished if DFS(v) has returned
• v.finish <= clock
CS 6301 IDSA 19
20
Classify Edges
• u.start < v.start < v.finish < u.finish
• v is reachable from u
• u is an ancestor of v in DFS tree
21
Classify Edges
• consider u->v and suppose v is new when DFS(u) begins
• u.start < v.start < v.finish < u.finish
• If DFS(u) calls DFS(v) directly, then u->v is a tree edge
• Otherwise u->v is a forward edge
22
Classify Edges
• consider u->v and v is finished when DFS(u) begins
• v.start < v.finish < u.start < u.finish, then u->v is a cross edge
23
Classify Edges
• consider u->v and v is active when DFS(u) begins
• v.start < u.start < u.finish < v.finish ,
• u->v is a back edge
Directed Acyclic Graph
• Source vertices have no
incoming edges
• Sink vertices have no outgoing
vertices
• DAG has at least one source
vertex and one sink vertex
• Is G a DAG?
CS 6301 IDSA
24
Is G a DAG?
25
What would you change to the code below?
dfs(v){
mark v
pre(v)
for each (v, w) in G do
if w is unmarked
w.parent = v
dfs(w)
post(v)
}
dfsAll(G){
initialize(G)
for each v in G do
unmark v
for each v in G d0
if v is unmarked
dfs(v)
}
Is G a DAG?
26
A linear time algorithm:
isDAG(v){
v.status = active
for each (v, w) in G do
if w.status is active
eturn false
else if w.status is new
if (!isDAG(w))
eturn false
v.status = finished
eturn true
}
isDAGAll(G){
for each v in G do
v.status = new
for each v in G d0
if v.status is new
if(!isDAG(v)) return false
eturn true
}
Topological Ordering
27
• Informally, place all vertices in a horizontal line
such that edges go only from left to right
• Topological ordering of G is a total order ‹, on
vertices such that
• u ‹ v for every edge u->v
• Topological ordering is only possible if G is a DAG
Topological Sort
28
Topological Sort
29
Topological Sort Algorithm
30
dfs(v){
mark v
pre(v)
for each (v, w) in G do
if v is unmarked
w.parent = v
dfs(w)
post(v)
}
dfsAll(G){
initialize(G)
for each v in G do
unmark v
for each v in G d0
if v is unmarked
dfs(v)
}
initialize(G) pre(v) post(v)
topList.addFirst(v)
Reverse of post order traversal
Problem of the day
31
Slide 1: DFS
Slide 2: DFS in a directed Graph
Slide 3: DFS
Slide 4: Preorder and postorder traversal of DFS Forest
Slide 5: Recursion Stack – Time diagram
Slide 6: Stack – Time diagram
Slide 7: Stack – Time diagram
Slide 8: Stack – Time diagram
Slide 9: Stack – Time diagram
Slide 10: Stack – Time diagram
Slide 11: Stack – Time diagram
Slide 12: Stack – Time diagram
Slide 13: Stack – Time diagram
Slide 14: Stack – Time diagram
Slide 15: Stack – Time diagram
Slide 16: Stack – Time diagram
Slide 17: Stack – Time diagram
Slide 18
Slide 19: Classifying Vertices
Slide 20
Slide 21
Slide 22
Slide 23
Slide 24: Directed Acyclic Graph
Slide 25: Is G a DAG?
Slide 26: Is G a DAG?
Slide 27: Topological Ordering
Slide 28: Topological Sort
Slide 29: Topological Sort
Slide 30: Topological Sort Algorithm
Slide 31: Problem of the day
PowerPoint Presentation
DFS
Sridhar Alaga
CS 6301 IDSA
DFS in a directed Graph
2
Use stack for DFS
dfs(v){
if v is unmarked
mark v
for each (v, w) in G do
dfs(w)
}
wfs(s){
put s into bag
while bag not empty
take v from bag
if v is unmarked
mark v
for each (v, w) in G do
put w in bag
}
DFS
3
Wrapper method to visit all nodes
dfs(v){
mark v
pre(v)
for each (v, w) in G do
if w is unmarked
w.parent = v
dfs(w)
post(v)
}
dfsAll(G){
initialize(G)
for each v in G do
unmark v
for each v in G do
if v is unmarked
dfs(v)
}
Preorder and postorder traversal of DFS Forest
4
dfs(v){
mark v
pre(v)
for each (v, w) in G do
if v is unmarked
w.parent = v
dfs(w)
post(v)
}
dfsAll(G){
initialize(G)
for each v in G do
unmark v
for each v in G d0
if v is unmarked
dfs(v)
}
initialize(G)
clock = 0
pre(v)
clock++
v.start = clock
post(v)
clock++
v.finish = clock
Record when a node entered and left stack
Recursion Stack – Time diagram
5
Stack – Time diagram
6
Stack – Time diagram
7
Stack – Time diagram
8
Stack – Time diagram
9
Stack – Time diagram
10
Stack – Time diagram
11
Stack – Time diagram
12
Stack – Time diagram
13
Stack – Time diagram
14
Stack – Time diagram
15
Stack – Time diagram
16
Stack – Time diagram
17
18
Preorde
postorde
Preorder and postorder traversal of DFS Forest
pre(v)
startList.add(v)
post(v)
finishList.add(v)
Classifying Vertices
• v is new if DFS(v) is not called
• clock < v.start
• v is active if DFS(v) is called but not returned
• v.start <= clock < v.finish
• v is finished if DFS(v) has returned
• v.finish <= clock
CS 6301 IDSA 19
20
Classify Edges
• u.start < v.start < v.finish < u.finish
• v is reachable from u
• u is an ancestor of v in DFS tree
21
Classify Edges
• consider u->v and suppose v is new when DFS(u) begins
• u.start < v.start < v.finish < u.finish
• If DFS(u) calls DFS(v) directly, then u->v is a tree edge
• Otherwise u->v is a forward edge
22
Classify Edges
• consider u->v and v is finished when DFS(u) begins
• v.start < v.finish < u.start < u.finish, then u->v is a cross edge
23
Classify Edges
• consider u->v and v is active when DFS(u) begins
• v.start < u.start < u.finish < v.finish ,
• u->v is a back edge
Directed Acyclic Graph
• Source vertices have no
incoming edges
• Sink vertices have no outgoing
vertices
• DAG has at least one source
vertex and one sink vertex
• Is G a DAG?
CS 6301 IDSA
24
Is G a DAG?
25
What would you change to the code below?
dfs(v){
mark v
pre(v)
for each (v, w) in G do
if w is unmarked
w.parent = v
dfs(w)
post(v)
}
dfsAll(G){
initialize(G)
for each v in G do
unmark v
for each v in G d0
if v is unmarked
dfs(v)
}
Is G a DAG?
26
A linear time algorithm:
isDAG(v){
v.status = active
for each (v, w) in G do
if w.status is active
eturn false
else if w.status is new
if (!isDAG(w))
eturn false
v.status = finished
eturn true
}
isDAGAll(G){
for each v in G do
v.status = new
for each v in G d0
if v.status is new
if(!isDAG(v)) return false
eturn true
}
Topological Ordering
27
• Informally, place all vertices in a horizontal line
such that edges go only from left to right
• Topological ordering of G is a total order ‹, on
vertices such that
• u ‹ v for every edge u->v
• Topological ordering is only possible if G is a DAG
Topological Sort
28
Topological Sort
29
Topological Sort Algorithm
30
dfs(v){
mark v
pre(v)
for each (v, w) in G do
if v is unmarked
w.parent = v
dfs(w)
post(v)
}
dfsAll(G){
initialize(G)
for each v in G do
unmark v
for each v in G d0
if v is unmarked
dfs(v)
}
initialize(G) pre(v) post(v)
topList.addFirst(v)
Reverse of post order traversal
Problem of the day
31
Slide 1: DFS
Slide 2: DFS in a directed Graph
Slide 3: DFS
Slide 4: Preorder and postorder traversal of DFS Forest
Slide 5: Recursion Stack – Time diagram
Slide 6: Stack – Time diagram
Slide 7: Stack – Time diagram
Slide 8: Stack – Time diagram
Slide 9: Stack – Time diagram
Slide 10: Stack – Time diagram
Slide 11: Stack – Time diagram
Slide 12: Stack – Time diagram
Slide 13: Stack – Time diagram
Slide 14: Stack – Time diagram
Slide 15: Stack – Time diagram
Slide 16: Stack – Time diagram
Slide 17: Stack – Time diagram
Slide 18
Slide 19: Classifying Vertices
Slide 20
Slide 21
Slide 22
Slide 23
Slide 24: Directed Acyclic Graph
Slide 25: Is G a DAG?
Slide 26: Is G a DAG?
Slide 27: Topological Ordering
Slide 28: Topological Sort
Slide 29: Topological Sort
Slide 30: Topological Sort Algorithm
Slide 31: Problem of the day