Lecture 5: Directed DFS, BFS, and Transitive Closure
CSC 226: Algorithms and Data Structures II Quinton Yong
quintonyong@ uvic.ca
Copyright By PowCoder代写 加微信 powcoder
Directed DFS
We can modify the traversal algorithms (DFS and BFS) for undirected graphs to directed graphs by traversing edges only along their direction.
In directed DFS, we have four types of edges:
Discovery edges lead to unvisited nodes in the traversal and form a spanning tree
Back edges go from nodes to one of its ancestors in the traversal discovery spanning tree
Forward edges go from nodes to one of its descendants in the traversal discovery spanning tree
Cross edges connect two nodes which do not have any ancestor and descendant relationship in the traversal discovery spanning tree
A directed DFS starting at a vertex 𝒔 determines the vertices reachable from 𝒔
Directed DFS
𝑫𝒊𝒓𝒆𝒄𝒕𝒆𝒅𝑫𝑭𝑺 (𝑮, 𝒖):
Input: Directed graph 𝑮 and vertex 𝒖 of 𝑮
Output: Labeling of edges in the connected component as discovery, back, forward, or cross edges
Label 𝒖 as active
for each outgoing edge 𝒆 do
if 𝒆 is unexplored then
𝒗 ← destination vertex of 𝒆
if 𝒗 is unexplored and not active then
Label 𝒆 as an explored discovery edge 𝑫𝒊𝒓𝒆𝒄𝒕𝒆𝒅𝑫𝑭𝑺(𝑮, 𝒗)
else if 𝒗 is active then
Label 𝒆 as an explored back edge
Label 𝒆 as an explored forward / cross edge Label 𝒖 as explored
Directed DFS
𝑫𝒊𝒓𝒆𝒄𝒕𝒆𝒅𝑫𝑭𝑺 (𝑮, 𝒖):
Input: Directed graph 𝑮 and vertex 𝒖 of 𝑮
Output: Labeling of edges in the connected component as discovery, back, forward, or cross edges
Label 𝒖 as active
for each outgoing edge 𝒆 do
if 𝒆 is unexplored then
𝒗 ← destination vertex of 𝒆
if 𝒗 is unexplored and not active then
Label 𝒆 as an explored discovery edge 𝑫𝒊𝒓𝒆𝒄𝒕𝒆𝒅𝑫𝑭𝑺(𝑮, 𝒗)
else if 𝒗 is active then
Label 𝒆 as an explored back edge
Label 𝒆 as an explored forward / cross edge Label 𝒖 as explored
Directed DFS
Discovery edges lead to unvisited nodes in the traversal and form a spanning tree
Back edges go from nodes to one of its ancestors in the traversal discovery spanning tree
𝟐 Forward edges go from nodes to one of its descendants in the traversal discovery spanning tree
Cross edges connect two nodes which do not have any ancestor and descendant relationship in the traversal discovery spanning tree
Directed BFS
In directed BFS, we have three types of edges:
Discovery edges lead to unvisited nodes in the traversal and form a spanning tree
Back edges go from nodes to one of its ancestors in the traversal discovery spanning tree
Cross edges connect two nodes which do not have any ancestor and descendant relationship in the traversal discovery spanning tree
A directed BFS starting at a vertex 𝒔 determines the vertices reachable from 𝒔
Directed BFS
Why can we have forward edges in Directed DFS but not BFS?
Forward edges go from nodes to one of its descendants in the traversal discovery spanning tree
Directed BFS
𝑫𝒊𝒓𝒆𝒄𝒕𝒆𝒅𝑩𝑭𝑺 (𝑮, 𝒖):
Input: Graph 𝑮 and vertex 𝒖 of 𝑮
Output: Labeling of edges in the connected component as discovery, back, or cross edges
𝑸 ← new empty queue
Label 𝒖 as explored
𝑸.enqueue(𝒖) 𝟒 while 𝑸 is not empty do
𝒖 ← 𝑸.dequeue()
for each outgoing edge 𝒆 do
𝒗 ← destination vertex of 𝒆 if 𝒆 is unexplored then
if 𝒗 is unexplored then
Label 𝒆 as an explored discovery edge Mark 𝒗 as explored
𝑸.enqueue(𝒗) else
Label 𝒆 as an explored back / cross edge
Directed BFS
𝑫𝒊𝒓𝒆𝒄𝒕𝒆𝒅𝑩𝑭𝑺 (𝑮, 𝒖):
Input: Graph 𝑮 and vertex 𝒖 of 𝑮
Output: Labeling of edges in the connected component as discovery, back, or cross edges
𝑸 ← new empty queue
Label 𝒖 as explored
𝑸.enqueue(𝒖) 𝟒 while 𝑸 is not empty do
𝒖 ← 𝑸.dequeue()
for each outgoing edge 𝒆 do
𝒗 ← destination vertex of 𝒆 if 𝒆 is unexplored then
if 𝒗 is unexplored then
Label 𝒆 as an explored discovery edge Mark 𝒗 as explored
𝑸.enqueue(𝒗) else
Label 𝒆 as an explored back / cross edge
Directed BFS Tree
Discovery edges lead to unvisited nodes in the traversal and form a spanning tree
Back edges go from nodes to one of its ancestors in the traversal discovery spanning tree
Cross edges connect two nodes which do not have any ancestor and descendant relationship in the traversal discovery spanning tree
Reachability
Given vertices 𝒖 and 𝒗 of a digraph, we say 𝒗 is reachable from 𝒖 if 𝑮 has a directed path from 𝒖 to 𝒗 𝟐𝟒
Example: 𝟎, 𝟐, and 𝟒 are reachable from 𝟑
Can determine the vertices reachable from a vertex 𝒖 by running directed DFS or BFS starting at 𝒖.
E.g. 𝑫𝒊𝒓𝒆𝒄𝒕𝒆𝒅𝑫𝑭𝑺 𝑮, 𝟑 : 𝟐𝟒
Transitive Closure
Given a directed graph 𝑮, the transitive closure 𝑮∗ of 𝑮 is the directed graph such that • 𝑮∗hasthesameverticesas𝑮
• If 𝑮 has a directed path from 𝒖 to 𝒗 (𝒖 ≠ 𝒗), 𝑮∗ has a directed edge from 𝒖 to 𝒗
The transitive closure provides information about reachability in the digraph.
Applications include:
• Finding possible flight paths
• Finding possible ways to deliver packets across the internet
Transitive Closure Algorithms
The transitive closure graph 𝑮∗ of a graph 𝑮 can be constructed in various ways:
• DFS or BFS for each vertex in the graph • Floyd-Warshall’salgorithm
• Matrix multiplication
The time complexity of transitive closure is 𝑶(𝒏𝟑), but some methods are more efficient in practice E.g. Using DFS:
Why is constructing the transitive closure using DFS inefficient?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com