Understanding Strongly Connected Components in Directed Graphs
Explore Strongly Connected Components (SCC) in graphs through Path-Based Depth-First Search Algorithm. Learn how SCCs are defined and identified in directed graphs using path connections between vertices. Dive into various examples showcasing different SCC configurations within graphs.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Strongly Connected Components (SCC) in a Graph Hamed Pouya 6/6/2025 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 3 4 6 6/6/2025 2
Path-Based Depth-First Search Algorithm [1] 6/6/2025 3
Path-Based Depth-First Search Alg. SCCs P a b c d e f 6/6/2025 4
Path-Based Depth-First Search Alg. SCCs P a a b c d e f 6/6/2025 5
Path-Based Depth-First Search Alg. SCCs P a a b b c d e f 6/6/2025 6
Path-Based Depth-First Search Alg. SCCs P a a b c b c d e f 6/6/2025 7
Path-Based Depth-First Search Alg. SCCs P a c a b b d e f 6/6/2025 8
Path-Based Depth-First Search Alg. SCCs P a c a b d b d e f 6/6/2025 9
Path-Based Depth-First Search Alg. SCCs P a c a b d b e d e f 6/6/2025 10
Path-Based Depth-First Search Alg. SCCs P a c a b d b e d e f 6/6/2025 11
Path-Based Depth-First Search Alg. SCCs P a c a b,d,e b d e f 6/6/2025 12
Path-Based Depth-First Search Alg. SCCs P a c a b,d,e f b d e f 6/6/2025 13
Path-Based Depth-First Search Alg. SCCs P a c a b,d,e f b d e f 6/6/2025 14
Path-Based Depth-First Search Alg. SCCs P a c a b,d,e,f b d e f 6/6/2025 15
Path-Based Depth-First Search Alg. SCCs P a c a b,d,e,f b d e f 6/6/2025 16
Path-Based Depth-First Search Alg. SCCs P a c a b,d,e,f 6/6/2025 17
Path-Based Depth-First Search Alg. SCCs P a c a b,d,e,f a 6/6/2025 18
Path-Based Depth-First Search Alg. SCCs P c b,d,e,f a 6/6/2025 19
Complexity ?(? + ?) 6/6/2025 20
Kosaraju-Sharir algorithm [2] 6/6/2025 21
Kosaraju-Sharir algorithm [2] a 0 - Seen, not finished yet. c b 0 - Finished. d e f 6/6/2025 22
Kosaraju-Sharir algorithm [2] a 1 - c b d e f 6/6/2025 23
Kosaraju-Sharir algorithm [2] a 1 - c 2 - b d e f 6/6/2025 24
Kosaraju-Sharir algorithm [2] a 1 - c 2 3 b d e f 6/6/2025 25
Kosaraju-Sharir algorithm [2] a 1 - c 2 3 b d e f 6/6/2025 26
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d e f 6/6/2025 27
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d 5 - e f 6/6/2025 28
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d 5 - e f 6 - 6/6/2025 29
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d 5 - e f 6 - 6/6/2025 30
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d 5 - e f 6 - 6/6/2025 31
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d 5 - e f 6 - 7 - 6/6/2025 32
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d 5 - e f 6 - 7 - 6/6/2025 33
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d 5 - e f 6 - 7 - 6/6/2025 34
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d 5 - e f 6 - 7 - 6/6/2025 35
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d 5 - e f 6 - 7 8 6/6/2025 36
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d 5 - e f 6 6 - 9 7 8 6/6/2025 37
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d 5 - e f 6 6 - 9 7 8 6/6/2025 38
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d 5 - e f 6 6 - 9 7 8 6/6/2025 39
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d 5 5 - 10 e f 6 6 - 9 7 8 6/6/2025 40
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d 5 5 - 10 e f 6 6 - 9 7 8 6/6/2025 41
Kosaraju-Sharir algorithm [2] a 1 - c 4 - 2 3 b d 5 5 - 10 e f 6 6 - 9 7 8 6/6/2025 42
Kosaraju-Sharir algorithm [2] a 1 - c 4 4 - 11 2 3 b d 5 5 - 10 e f 6 6 - 9 7 8 6/6/2025 43
Kosaraju-Sharir algorithm [2] a 1 1 - 12 c 4 4 - 11 2 3 b d 5 5 - 10 e f 6 6 - 9 7 8 6/6/2025 44
Kosaraju-Sharir algorithm [2] a ?,?,?,?,?,? 1 1 - 12 c 4 4 - 11 2 3 b d 5 5 - 10 e f 6 6 - 9 7 8 6/6/2025 45
Kosaraju-Sharir algorithm [2] a c b d e f 6/6/2025 46
Kosaraju-Sharir algorithm [2] a c b d e f 6/6/2025 47
Kosaraju-Sharir algorithm [2] a ?,?,?,?,?,? c b d e f 6/6/2025 48
Kosaraju-Sharir algorithm [2] SCCs a ?,?,?,?,?,? ? c b d e f 6/6/2025 49
Kosaraju-Sharir algorithm [2] SCCs a ?,?,?,?,?,? ? c b d e f 6/6/2025 50
