• Problems on DFS

Problems on DFS

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

1. Problem 2

Back to DFS

Data Structures and Algorithms Table of Contents

---

anusha-murali.github.io