Strongly Connected Components

Strongly Connected Components

1. Strongly Connected Components
Prepared by
Md. Shafiuzzaman
Lecturer, Dept. of CSE, JUST

2. Md. Shafiuzzaman 2
Strongly Connected Components
Adirectedgraphisstronglyconnectedifthereisapathbetween
allpairsofvertices.
Astronglyconnectedcomponent(SCC)ofadirectedgraphisa
maximalstronglyconnectedsubgraph.

3. Md. Shafiuzzaman 3
Strongly Connected Components
astronglyconnectedcomponent(SCC)ofadirectedgraph
G(V,E)isamaximalsetofverticesUVsuchthat
–For each u,v U we have both uvand vu
i.e., u andvare mutually reachablefrom each other (uv)
Let G
T
(V,E
T
) be the transposeof G(V,E) where
E
T
{(u,v): (u,v) E}
–i.e., E
T
consists of edges of Gwith their directions reversed
Constructing G
T
from Gtakes O(V+E) time (adjacency list rep)
Note: Gand G
T
have the same SCCs (uv inGuv inG
T
)

4. Md. Shafiuzzaman 4
Strongly Connected Components
Algorithm
(1)Run DFS(G) to compute finishing times for all uV
(2)Compute G
T
(3)Call DFS(G
T
) processing vertices in main loop in
decreasing f[u] computed in Step (1)
(4)Output vertices of each DFTin DFFof Step (3)as a
separate SCC

5. Md. Shafiuzzaman 5
SCC: Examplea b c
e
d
f g h

6. Md. Shafiuzzaman 6
SCC: Examplea b c
e
d
f g h
1
1
(1)Run DFS(G) to compute finishing times for all uV

7. Md. Shafiuzzaman 7
SCC: Examplea b c
e
d
f g h
1
1
10
2734 56
89
(1)Run DFS(G) to compute finishing times for all uV

8. Md. Shafiuzzaman 8
SCC: Examplea b c
e
d
f g h
1
2
10
2734 56
8911
(1)Run DFS(G) to compute finishing times for all uV

9. Md. Shafiuzzaman 9
SCC: Examplea b c
e
d
f g h
1
2
10
2734 56
8916111413
1512
1
Vertices sorted according to the finishing times:
b, e, a, c, d, g, h, f 

10. Md. Shafiuzzaman 10
SCC: Examplea b c
e
d
f g h
(2)Compute G
T

11. Md. Shafiuzzaman 11
SCC: Examplea b c
e
d
f g h
(3) Call DFS(G
T
) processing vertices in main loop in
decreasing f[u] order:b, e, a, c, d, g, h, f 

12. Md. Shafiuzzaman 12
SCC: Examplea b c
e
d
f g h
r
1
=
(3) Call DFS(G
T
) processing vertices in main loop in
decreasing f[u] order:b, e, a, c, d, g, h, f 

13. Md. Shafiuzzaman 13
SCC: Examplea b c
e
d
f g h
r
1
=
(3) Call DFS(G
T
) processing vertices in main loop in
decreasing f[u] order:b, e, a, c, d, g, h, f 

14. Md. Shafiuzzaman 14
SCC: Examplea b c
e
d
f g h
r
1
= r
2
=
(3) Call DFS(G
T
) processing vertices in main loop in
decreasing f[u] order:b, e, a, c, d, g, h, f 

15. Md. Shafiuzzaman 15
SCC: Examplea b c
e
d
f g h
r
1
= r
2
=
(3) Call DFS(G
T
) processing vertices in main loop in
decreasing f[u] order:b, e, a, c, d, g, h, f 

16. Md. Shafiuzzaman 16
SCC: Examplea b c
e
d
f g h
r
1
= r
2
=
r
3
=
(3) Call DFS(G
T
) processing vertices in main loop in
decreasing f[u] order:b, e, a, c, d, g, h, f 

17. Md. Shafiuzzaman 17
SCC: Examplea b c
e
d
f g
h
r
1
= r
2
=
r
3
=
(3) Call DFS(G
T
) processing vertices in main loop in
decreasing f[u] order:b, e, a, c, d, g, h, f 

18. Md. Shafiuzzaman 18
SCC: Examplea b c
e
d
f g h
r
1
= r
2
=
r
3
= r
4
=
(3) Call DFS(G
T
) processing vertices in main loop in
decreasing f[u] order:b, e, a, c, d, g, h, f 

19. Md. Shafiuzzaman 19
SCC: Examplea b c
e
d
f g h
r
1
= r
2
=
r
3
= r
4
=
(4) Output vertices of each DFTin DFFas a separate SCC
C
b{b,a,e}
C
g{g,f} C
h{h}
C
c{c,d}

20. Md. Shafiuzzaman 20
SCC: Examplea b c
e
d
f g h
hf,g
c,d
a,b,e
Acyclic component
graph
C
b C
g
C
c
C
h