Anusha Murali

Logo

Please see github.com/anusha-murali for all of my repositories.

View GitHub Profile

Problems on DFS

  1. Find all SCC’s in the following graph.

    scc_problem1

    We first find $G^R$ by reversing the direction of all the edges in $G$:

    scc_problem1_b

    Then we run DFS on $G^R$ and enumerate the vertices in decreasing postorder number:

    scc_problem1_c

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)$.

scc_problem1_d

  1. Problem 2

Back to DFS

Data Structures and Algorithms Table of Contents


anusha-murali.github.io