Strongly Connected Components (SCC) in a Graph Hamed Pouya

Strongly Connected Components (SCC) in a Graph Hamed Pouya 06/25/2023 1

Strongly Connected Components A subset of a directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the subset. 2 5 7 1 06/25/2023 3 4 6 2

Path-Based Depth-First Search Algorithm [1] 06/25/2023 3

Path-Based Depth-First Search Alg. SCCs P a b c d e 06/25/2023 f 4

Path-Based Depth-First Search Alg. SCCs P a a b c d e 06/25/2023 f 5

Path-Based Depth-First Search Alg. SCCs P a a b b c d e 06/25/2023 f 6

Path-Based Depth-First Search Alg. SCCs P a a b c b c d e 06/25/2023 f 7

Path-Based Depth-First Search Alg. SCCs P {c } a a b b d e 06/25/2023 f 8

Path-Based Depth-First Search Alg. SCCs P {c } a a b d b d e 06/25/2023 f 9

Path-Based Depth-First Search Alg. SCCs P {c } a a b d b e d e 06/25/2023 f 10

Path-Based Depth-First Search Alg. SCCs P {c } a a b d b e d e 06/25/2023 f 11

Path-Based Depth-First Search Alg. SCCs P {c } a a b,d,e b d e 06/25/2023 f 12

Path-Based Depth-First Search Alg. SCCs P {c } a a b,d,e f b d e 06/25/2023 f 13

Path-Based Depth-First Search Alg. SCCs P {c } a a b,d,e f b d e 06/25/2023 f 14

Path-Based Depth-First Search Alg. SCCs P {c } a a b,d,e,f b d e 06/25/2023 f 15

Path-Based Depth-First Search Alg. SCCs P {c } a a b,d,e,f b e 06/25/2023 d f 16

Path-Based Depth-First Search Alg. SCCs {c } { b ,d ,e ,f } 06/25/2023 P a a 17

Path-Based Depth-First Search Alg. SCCs {c } { b ,d ,e ,f } {a } 06/25/2023 P a a 18

Path-Based Depth-First Search Alg. SCCs P {c } { b ,d ,e ,f } {a } 06/25/2023 19

Complexity 𝑂 (𝐸 𝑉 ) 06/25/2023 20

Kosaraju-Sharir algorithm [2] 06/25/2023 21

Kosaraju-Sharir algorithm [2] a 0 0 - - Seen, not finished yet. Finished. c b d e 06/25/2023 f 22

Kosaraju-Sharir algorithm [2] a 1 - c b d e 06/25/2023 f 23

Kosaraju-Sharir algorithm [2] a 1 - 2 b - c d e 06/25/2023 f 24

Kosaraju-Sharir algorithm [2] a 1 - 2 b 3 c d e 06/25/2023 f 25

Kosaraju-Sharir algorithm [2] a 1 - 2 b 3 c d e 06/25/2023 f 26

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c d e 06/25/2023 f 27

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c d 5 e 06/25/2023 - f 28

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c d 5 e 06/25/2023 6 - - f 29

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c d 5 e 06/25/2023 6 - - f 30

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c d 5 e 06/25/2023 6 - - f 31

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c 7 - f d 5 e 06/25/2023 6 - - 32

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c 7 - f d 5 e 06/25/2023 6 - - 33

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c 7 - f d 5 e 06/25/2023 6 - - 34

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c 7 - f d 5 e 06/25/2023 6 - - 35

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c 7 8 f d 5 e 06/25/2023 6 - - 36

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c 7 8 f d 5 e 06/25/2023 6 9 - 37

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c 7 8 f d 5 e 06/25/2023 6 9 - 38

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c 7 8 f d 5 e 06/25/2023 6 9 - 39

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c 7 8 f d 5 e 06/25/2023 6 9 -10 40

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c 7 8 f d 5 e 06/25/2023 6 9 -10 41

Kosaraju-Sharir algorithm [2] a 1 b 4 - - 2 3 c 7 8 f d 5 e 06/25/2023 6 9 -10 42

Kosaraju-Sharir algorithm [2] a 1 b 4 - 11 - 2 3 c 7 8 f d 5 e 06/25/2023 6 9 -10 43

Kosaraju-Sharir algorithm [2] a 1 b 4 -12 11 - 2 3 c 7 8 f d 5 e 06/25/2023 6 9 -10 44

Kosaraju-Sharir algorithm [2] a 1 b 4 { 𝑎 , 𝑏,𝑑,𝑒 , 𝑓 , 𝑐 } -12 11 - 2 3 c 7 8 f d 5 e 6 9 06/25/2023 -10 45

Kosaraju-Sharir algorithm [2] a c b d e 06/25/2023 f 46

Kosaraju-Sharir algorithm [2] a c b d e 06/25/2023 f 47

Kosaraju-Sharir algorithm [2] a { 𝑎 ,𝑏, 𝑑, 𝑒 , 𝑓 ,𝑐 } c b d e 06/25/2023 f 48

Kosaraju-Sharir algorithm [2] SCCs a { 𝑎 ,𝑏, 𝑑, 𝑒 , 𝑓 ,𝑐 } {𝑎 } c b d e 06/25/2023 f 49

Kosaraju-Sharir algorithm [2] SCCs a { 𝑎 ,𝑏, 𝑑, 𝑒 , 𝑓 ,𝑐 } {𝑎 } c b d e 06/25/2023 f 50

Kosaraju-Sharir algorithm [2] SCCs a { 𝑎 ,𝑏, 𝑑, 𝑒 , 𝑓 ,𝑐 } {𝑎 } { 𝑏, 𝑑 , 𝑒, 𝑓 } c b d e 06/25/2023 f 51

Kosaraju-Sharir algorithm [2] SCCs a { 𝑎 ,𝑏, 𝑑, 𝑒 , 𝑓 ,𝑐 } {𝑎 } { 𝑏, 𝑑 , 𝑒, 𝑓 } c b d e 06/25/2023 f 52

Kosaraju-Sharir algorithm [2] SCCs a { 𝑎 ,𝑏, 𝑑, 𝑒 , 𝑓 ,𝑐 } {𝑎 } { 𝑏, 𝑑 , 𝑒, 𝑓 } {𝑐 } c b d e 06/25/2023 f 53

Complexity 𝑂 (𝐸 𝑉 ) 06/25/2023 54

Comparison Tarjan’s Alg. 06/25/2023 Path-Based Alg. Kosaraju-Sharir Alg. 55

References [1] H. N. Gabow, “Path-based depth-first search for strong and biconnected components,” Information Processing Letters, vol. 74, no. 3-4, pp. 107–114, 2000. [2] M. Sharir, “A strong-connectivity algorithm and its applications in data flow analysis,” Computers & Mathematics with Applications, vol. 7, no. 1, pp. 67–72, 1981. 06/25/2023 56