🌵
Christian's Wiki
/
📖
Data Structures & Algorithms
/
Algorithm
/
Strongly Connected Components

Strongly Connected Components

‣
Graph Theory: What is a strongly connected component? How would you find strongly connected components for a graph G? Implement it

Strongly Connected Components Kosaraju's Algorithm Graph Algorithm: https://www.youtube.com/watch?v=RpgcYiky7uw

A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph. For example, there are 3 SCCs in the following graph.

image
‣
SCC's can be found using Korasaju's Algorithm
  1. Initialize with stack and set of visited vertices
  2. Do DFS on all vertices, while maintaining:
    1. Visited vertices upon seeing it
    2. And putting completed vertices in the stack upon finishing (track finish times)
  3. Reverse all edges
  4. Do DFS from elements popped in the stack while mantaining
    1. Another visited set
    2. Strongly connected components where each SCC consists of vertices reachable from the popped element
image