Please see github.com/anusha-murali for all of my repositories.
Find all SCC’s in the following graph.
We first find $G^R$ by reversing the direction of all the edges in $G$:
Then we run DFS on $G^R$ and enumerate the vertices in decreasing postorder number:
The postorder numbers of DFS on $G^R$ are shown in red. Therefore, the vertices in decreasing postorder number are:
\[B, G, C, A, D, H, E, F.\]Now, run DFS on the original graph $G$ in the order of the above decreasing postorder numbers. We first start from vertex $B$ and get stuck after traversing $B, G,$ and $C$. So, $DFS(B) = {B, G, C}$.
Now we start DFS on $A$ and find $DFS(A) = {A}$.
Then we start DFS on $D$ and find $DFS(D) = {D, H, E}$.
Finally, we start DFS on $F$ and find $DFS(F) = {F}$.
Therefore, there are 4 SCCs in the given graph $G$, namely $(B, G, C), (A), (D, H, E),$ and $(F)$.
Data Structures and Algorithms Table of Contents