DFS (Depth first search) for graph

What is dfs?
 This algorithm explores aggressively and backtracks only when necessary. This is similar to how we play a maze game.

To code DFS iteratively, we can mimic BFS , but use a Stack instead of a Queue. Another way to code this would be to do it recursively. DFS is very naturally phased as recursive example. We will see both of implementation later.

 DFS(graph G, vertex s)
     mark s as explored
     for every edge (s, v):
          if v unexplored
               DFS(G, v)

Example : 
Consider the graph:

So, our strategy will be to explore aggressively and only backtrack when necessary.
Example taken from coursera course by Tim Roughgarden in Algorithms: Design and Analysis, Part 1.

Now, we have starting vertex as s.  From s we have to go to some node, lets go to a.

From as we can't go to b, as it is s's immediate neighbor, but we can go to a's immediate neighbor. So we go to c:

From c, we go to e.

From e we can go to d only as it is the only neighbor which is unexplored. So d is 5th node we see.

From d we can either go to c or we can go b. Lets suppose we go to c. But c is already explored at number 3, so we retreat, and we then go to b.

Now at b we go to s, but we have explored that, then we go to a, we have explored. So we have explored all the options from b, so we retreat to d, then we see that at d also we have explored all the options, so we retreat to e, from e to c, from c to a, and then we come to s back. From s we have not went through edge s-b, so we traverse and again retreat as we have already seen b. Now we have covered all the edges.

Basic DFS Properties
At the end of DFS, all vertices that could have been reached will have been reached.
Time complexity - 
Running time for adjacency list- O(|V|+|E|) OR O(n+m) where |V| and |E| is number of vertices and edges for adjacency list representation of graph.
Running time for adjacency matrix - O(|V|²) OR O(n²) as we have to traverse through the whole row until we find an edge.

Application of DFS

1. Topological sorting
2. Finding SCC(strongly connected component)