𝒗𝟏 𝒗𝟐 𝒗𝟑 𝒗𝟒 𝒗𝟓 𝒗𝟔 𝒗𝟕 𝒗𝟖 𝒗𝟗
Lecture 14: Topological Sort
CSC 226: Algorithms and Data Structures II Quinton Sort
• Adirectedacyclicgraphdefinesapartialorder(waytocomparevertices<,=,>)
Copyright By PowCoder代写 加微信 powcoder
• Hence, a graph can be partially sorted
• Applications:
• Nodes are tasks or work assignments
• Edges represent dependencies among tasks (precedence relationships)
• Task 𝒃 cannot start until task 𝒂 is completed
• Course prerequisites
• Inheritance between Java classes
• Compilationdependencygraph
DAGs and Topological Ordering
• A directed acyclic graph (DAG) is a digraph that has no directed cycles Directed acyclic graph 𝑮
Directed cycle
• A topological ordering of a digraph is a numbering 𝒗𝟏, … , 𝒗𝒏 of the vertices such that for every directededge 𝒗𝒊,𝒗𝒋 ,wehave𝒊<𝒋inthenumbering.
Topological ordering of 𝑮 𝒗𝟐 𝒗𝟏
𝒗𝟏 𝒗𝟐 𝒗𝟑 𝒗𝟒 𝒗𝟓
• Theorem: A digraph admits a topological ordering if and only if it is a DAG
No topological ordering
CSC CSC 227 228
DAGs and Topological Ordering
• Number vertices so that having edge (𝒗𝒊, 𝒗𝒋) implies 𝒊 < 𝒋 in numbering
Coffee Nap
Study CSC Write Code
Study More
Dream about graphs
Topological Sort Algorithm (Iterative)
• If a digraph is acyclic, then there must exist a node 𝒗𝟏 with 𝐢𝐧𝐝𝐞𝐠 𝒗𝟏
• Remove 𝒗𝟏 and all its outgoing edges
• Theresultinggraphmustalsobeacyclic
• Removing a vertex from an acyclic graph can’t create a cycle
• Remove the next vertex 𝒗𝟐 with 𝐢𝐧𝐝𝐞𝐠 𝒗𝟐
• Repeat until all vertices are removed
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
1 𝒆𝒆2 2 𝒈𝒈
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
1 𝒆𝒆2 2 𝒈𝒈
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
1 𝒆𝒆2 2 𝒈𝒈
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
1 𝒆𝒆1 2 𝒈𝒈
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
𝒗𝟏 𝒗𝟐 𝒗𝟑 𝒗𝟒 𝒗𝟓 𝒗𝟔 𝒗𝟕 𝒗𝟖 𝒗𝟗
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
𝒗𝟏 𝒗𝟐 𝒗𝟑 𝒗𝟒 𝒗𝟓 𝒗𝟔 𝒗𝟕 𝒗𝟖 𝒗𝟗
Topological Sort Algorithm (Iterative) Running Time
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
𝑶 𝒎 since sum of all degrees is 𝑶(𝒎)
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
1 𝒆𝒆2 2 𝒈𝒈
Consider if 𝑮 has a directed cycle
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
Topological Sort Algorithm (Iterative)
𝑻𝒐𝒑𝒐𝒍𝒐𝒈𝒊𝒄𝒂𝒍𝑺𝒐𝒓𝒕(𝑮):
Input: Digraph 𝑮 with 𝒏 vertices
Output: Topological ordering of 𝑮 or an indication of a directed cycle
𝑺 ← empty stack
for each vertex 𝒖 in 𝑮 do
ifdeg 𝒖 =0then 𝑺. 𝒑𝒖𝒔𝒉(𝒖)
while 𝑺 is not empty do
𝒖 ← 𝑺. 𝒑𝒐𝒑()
Number 𝒖 as vertex 𝒗𝒊
for each vertex 𝒗 adjacent to 𝒖 do
deg 𝒗 ← deg 𝒗 − 𝟏 ifdeg 𝒗 =𝟎then
𝑺. 𝒑𝒖𝒔𝒉(𝒗) if 𝒊 > 𝒏 then
return 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏
return “𝑮 has a directed cycle”
Topological Sort using DFS Reverse Postorder
• DFS Postorder: Assign a vertex numbering when it has no more unexplored outgoing edges
• Reverse postorder numbering is when numbering starts at 𝒏
• The DFS reverse postorder numbering is a topological order numbering 𝒂
Topological Sort using DFS Reverse Postorder
• DFS Postorder: Assign a vertex numbering when it has no more unexplored outgoing edges
• Reverse postorder numbering is when numbering starts at 𝒏
• The DFS reverse postorder numbering is a topological order numbering 𝒂
Topological Sort using DFS Reverse Postorder
• DFS Postorder: Assign a vertex numbering when it has no more unexplored outgoing edges
• Reverse postorder numbering is when numbering starts at 𝒏
• The DFS reverse postorder numbering is a topological order numbering
Topological Sort using DFS Reverse Postorder
• DFS Postorder: Assign a vertex numbering when it has no more unexplored outgoing edges
• Reverse postorder numbering is when numbering starts at 𝒏
• The DFS reverse postorder numbering is a topological order numbering
𝒗 𝒆𝒗 𝒃𝒂𝒄𝒅𝒆𝒇𝒈𝒉𝒊 𝟔𝟓
• Runningtimeis𝑶(𝒏+𝒎)
𝒗𝟏 𝒗𝟐 𝒗𝟑 𝒗𝟒 𝒗𝟓 𝒗𝟔 𝒗𝟕 𝒗𝟖 𝒗𝟗
Topological Sort using DFS Reverse Postorder
• DFS Postorder: Assign a vertex numbering when it has no more unexplored outgoing edges
• Reverse postorder numbering is when numbering starts at 𝒏
• The DFS reverse postorder numbering is a topological order numbering
Consider if 𝑮 has a directed cycle 𝒄𝒄
• Runningtimeis𝑶(𝒏+𝒎)
Topological Sort using DFS Reverse Postorder
• DFS Postorder: Assign a vertex numbering when it has no more unexplored outgoing edges
• Reverse postorder numbering is when numbering starts at 𝒏
• The DFS reverse postorder numbering is a topological order numbering 𝒂𝒂
• Runningtimeis𝑶(𝒏+𝒎)
Topological Sort using DFS Reverse Postorder
• DFS Postorder: Assign a vertex numbering when it has no more unexplored outgoing edges
• Reverse postorder numbering is when numbering starts at 𝒏
• The DFS reverse postorder numbering is a topological order numbering
Back edge means a directed cycle was detected 𝒃𝒃
• Runningtimeis𝑶(𝒏+𝒎)
Topological Sort and SCCs
• Computethestronglyconnectedcomponentstoproduceareduceddirectedacyclicgraph
Sort the directed acyclic graph using topological sort
Note: both post order numberings and topological numberings may not be unique
Time Complexity of DFS Applications
Theorem: The time complexity of DFS traversal for a graph 𝑮 = 𝑽, 𝑬 for
• Testingwhether𝑮isconnected
• Computing a spanning forest of 𝑮
• Computing a path between two vertices in 𝑮 or reporting no path exists
• Computing a cycle in 𝑮 or reporting that no cycles exist
• Identifying the strongly connected components of 𝑮
• Computing a topological sort of 𝑮
is𝑶(𝒏+𝒎)where𝒏= 𝑽 and𝒎= 𝑬.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com