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.
mailto:
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
A B C
D E
F G
H
BCDE A
H
G F Note: Metagraph is a DAG!
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?
A) G and GR have the same number of vertices.
B) G and GR have the same number of edges.
C) G = (GR)R.
D) 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
A B C
D E
F G
H
1
2
3
4
5 6
7
8
9
10
11
12
13
14
15
16