Announcements
Announcements
Homework 0 Solutions online
Homework 1 Due on Friday
Exam 1 Next Friday
If you cannot take the exam during class hours, please email me at letting me know what times might work for you.
Strongly Connected Components
Definition: In a directed graph G, two vertices v and w are in the same Strongly Connected Component (SCC) if v is reachable from w and w is reachable from v.
Today
Metagraphs
Computing strongly connected components
Shortest path algorithms (Ch 4)
Connectivity
Do strongly connected components completely describe connectivity in G?
No! In directed case, can have edges between SCCs.
Need extra information to describe how SCCs connect.
v
w
Metagraph
Definition: The metagraph of a directed graph G is a graph whose vertices are the SCCs of G, where there is an edge between C1 and C2 if and only if G has an edge between some vertex of C1 and some vertex of C2.
Example
Note: Metagraph is a DAG!
A
B
C
D
E
F
G
H
BCDE
A
H
G
F
Result
Theorem: The metagraph is any directed graph is a DAG.
Proof (sketch):
Assume for sake of contradiction it is not.
Then metagraph has a cycle.
Use this to show that separated components should be connected.
Proof
G
MG
A
B
C
D
E
A
B
C
D
E
Computing SCCs
Problem: Given a directed graph G compute the SCCs of G and its metagraph.
Easy Algorithm:
For each v compute vertices reachable from v.
Find pairs v, w so that v reachable from w and visa versa.
For each v the corresponding w’s are the SCC of v.
Runtime: O(|V|(|V|+|E|)). We can do better.
Observation
Suppose that SCC(v) is a sink in the metagraph.
G has no edges from SCC(v) to another SCC.
Run explore(v) to find all vertices reachable from v.
Contains all vertices in SCC(v).
Contains no other vertices.
If v in sink SCC, explore(v) finds exactly v’s component.
Strategy
Find v in a sink SCC of G.
Run explore(v) to find component C1.
Repeat process on G-C1.
Problem: How do we find v?
Result
Proposition: Let C1 and C2 be SCCs of G with an edge from C1 to C2. If we run DFS on G, the largest postorder number of any vertex in C1 will be larger than the largest postorder number in C2.
C1
C2
Why do we Care?
Let v be the vertex with the largest postorder number.
There is no edge to SCC(v) from any other SCC.
SCC is a source SCC.
But we want a sink SCC.
A sink is like a source, only with the edges going in the opposite direction.
Reverse Graph
Definition: Given a directed graph G, the reverse graph of G (denoted GR) is obtained by reversing the directions of all of the edges of G.
A
B
C
A
B
C
Question: Reverse Graph Properties
Which of the following are true about reverse graphs?
G and GR have the same number of vertices.
G and GR have the same number of edges.
G = (GR)R.
A vertex has as many ingoing/outgoing edges in G as it does in GR.
Other Properties of Reverse Graphs
Given a directed graph G and its reverse graph GR:
G and GR have the same SCCs.
The sink SCCs of G are the source SCCs of GR.
The source SCCs of G are the sink SCCs of GR.
So we can find a sink SCC of G, by finding a source SCC of GR!
Proposition Reminder
Proposition: Let C1 and C2 be SCCs of G with an edge from C1 to C2. If we run DFS on G, the largest postorder number of any vertex in C1 will be larger than the largest postorder number in C2.
C1
C2
Proof I
If DFS discovers a vertex in C1 before C2:
First vertex discovered is v.
All of C1 and C2 downstream of v.
DFS will discover the rest of C1 and C2 while exploring v.
v has largest postorder in C1 or C2.
Proof II
If DFS discovers a vertex in C2 before C1:
First vertex discovered is w.
DFS will find all of C2 while exploring w.
C1 cannot be reached from w.
Otherwise they’d be the same SCC.
Every vertex in C1 discovered after w finished.
C1 has larger posts than C2.
C1
C2
w
Algorithm
SCCs(G)
Run DFS(GR) record postorder
Find v with largest v.post
Set all vertices unvisited
Run explore(v)
Let C be the visited vertices
Return SCCs(G-C) ∪ {C}
O(|V|+|E|)
Final Runtime: O((|V|+|E|)(#SCCs))
Still Too Slow
Problem: We recompute the postorder for every SCC we need to find.
Solution: We don’t have to do this. After removing some SCCs to get G’, the largest postorder number of vertices in G’ is still in a sink component of G’.
Algorithm II
SCCs(G)
Run DFS(GR) record postorders
Mark all vertices unvisited
For v ∈ V in reverse postorder
If v not in a component yet
explore(v) on
G-components found,
marking new component
If not v.visited
explore(v) mark component
Just 2 DFSs! Runtime O(|V|+|E|).
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
A
B
C
D
E
F
G
H