Lecture 13: Strongly Connected Components
CSC 226: Algorithms and Data Structures II Quinton
Given vertices 𝒖 and 𝒗 of a digraph, we say 𝒗 is reachable from 𝒖 if 𝑮 has a directed path from 𝒖 to 𝒗 𝟐𝟒
Example: 𝟎, 𝟐, and 𝟒 are reachable from 𝟑
Copyright By PowCoder代写 加微信 powcoder
Can determine the vertices reachable from a vertex 𝒖 by running directed DFS or BFS starting at 𝒖.
E.g. 𝑫𝒊𝒓𝒆𝒄𝒕𝒆𝒅𝑫𝑭𝑺 𝑮, 𝟑 : 𝟐𝟒
Strongly Connected Digraphs
Given vertices 𝒖 and 𝒗 of a digraph, we say 𝒗 is reachable from 𝒖 if 𝑮 has a directed path from 𝒖 to 𝒗 A digraph 𝑮 is connected if every pair of vertices is connected by an undirected path
Connected Digraph
A digraph 𝑮 is strongly connected if for every pair of vertices 𝒖 and 𝒗 of 𝑮, 𝒖 is reachable from 𝒗 and 𝒗 is reachable from 𝒖.
• i.e. Everything is reachable from everything else 𝒂𝒈
Strongly Connected Digraph
Strong Connectivity
“Each vertex can reach all other vertices”
• One way to determine if a digraph is strongly connected is by running directed DFS starting from every vertex
• This is inefficient since this takes 𝑶 𝒏 𝒏 + 𝒎 time
It turns out that we can determine if a graph is strongly connected by running DFS only twice
Strong Connectivity Algorithm
Run first DFS starting from any vertex 𝒖 on 𝑮.
• If every vertex is reached, we know that 𝒖 can reach every other vertex
Run second DFS starting from 𝒖 on the reversed graph 𝑮𝑹 (𝑮 with all edges reversed)
• If every vertex is reached, we know that 𝒖 is reachable from every other vertex
Running time: 𝑶(𝒏 + 𝒎)
Strongly Connected Components
• A strongly connected component (SCC) of a digraph is a maximal subset of nodes in which each node is reachable from every other node in the set
Three SCCs
• Identifying the SCCs of a graph is an important preprocessing step for many graph algorithms (e.g. topological sort)
• SCCs can also be used for graph analysis (e.g. reachability, social networks)
DFS Postorder Numbering
Perform DFS and assign a vertex a number when it has no more unexplored outgoing edges • Vertices ordered by when you are “done with them” during DFS
E.g. 𝑫𝒊𝒓𝒆𝒄𝒕𝒆𝒅𝑫𝑭𝑺 𝑮, 𝒂 :
DFS Postorder Numbering
Perform DFS and assign a vertex a number when it has no more unexplored outgoing edges • Vertices ordered by when you are “done with them” during DFS
E.g. 𝑫𝒊𝒓𝒆𝒄𝒕𝒆𝒅𝑫𝑭𝑺 𝑮, 𝒂 :
DFS Postorder Numbering:
SCC Algorithm: Kosaraju’s Algorithm
• Perform a postorder number using DFS on 𝑮 starting at any vertex 𝒖
• Construct a reversed graph 𝑮𝑹 by reversing each edge in 𝑮
• Computespanningforest(discoveryedges)of𝑮usingDFSon𝑮𝑹starting at node with highest remaining postorder number
• The resulting trees are the SCCs 𝒂𝒃
SCC Algorithm: Kosaraju’s Algorithm
• Perform a postorder number using DFS on 𝑮 starting at any vertex 𝒖
• Construct a reversed graph 𝑮𝑹 by reversing each edge in 𝑮
• Computespanningforest(discoveryedges)of𝑮usingDFSon𝑮𝑹starting at node with highest remaining postorder number
• The resulting trees are the SCCs 𝒂𝒃
SCC Algorithm: Kosaraju’s Algorithm
• Perform a postorder number using DFS on 𝑮 starting at any vertex 𝒖
• Construct a reversed graph 𝑮𝑹 by reversing each edge in 𝑮
• Computespanningforest(discoveryedges)of𝑮usingDFSon𝑮𝑹starting at node with highest remaining postorder number
• The resulting trees are the SCCs 𝒂𝒃
𝒆 𝒅𝒄𝒇𝒆𝒃𝒂 123456
SCC Algorithm: Kosaraju’s Algorithm
• Perform a postorder number using DFS on 𝑮 starting at any vertex 𝒖
• Construct a reversed graph 𝑮𝑹 by reversing each edge in 𝑮
• Computespanningforest(discoveryedges)of𝑮usingDFSon𝑮𝑹starting at node with highest remaining postorder number
• The resulting trees are the SCCs 𝒂𝒃
𝒆 𝒅𝒄𝒇𝒆𝒃𝒂 123456
SCC Algorithm: Kosaraju’s Algorithm
• Perform a postorder number using DFS on 𝑮 starting at any vertex 𝒖
• Construct a reversed graph 𝑮𝑹 by reversing each edge in 𝑮
• Computespanningforest(discoveryedges)of𝑮usingDFSon𝑮𝑹starting at node with highest remaining postorder number
• The resulting trees are the SCCs
Kosaraju’salgorithmtakes𝑶𝒏+𝒎 time
SCC and Reduced Graphs
“Vertices in each SCC merged into a single vertex”
In the reduced graph 𝑮𝒓 = (𝑽𝒓, 𝑬𝒓) of 𝑮
• 𝑽𝒓 corresponds to the SCCs of 𝑮
• 𝑬𝒓 represent the cross-component edges (edges between SCCs)
Reduced graphs are directed acyclic graphs
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com