# Depth First Search (DFS)

In last post, we learned graph basics and how graphs are represented in programming model. We studied various advantages and disadvantages of adjacency matrix and adjacency list representation of graphs. Today, let’s us discuss traversals of graph. Two kinds of traversals are possible on graph : **Depth First search, **commonly known as** DFS **and** Breadth First Search,** commonly called as** BFS. **

Depth First Search or traversal explores a given graph depth wise, that means we go down the graph from one node to another till there is no unexplored node down. Once we reach the end of a path going down, backtracking starts and parent of current node is looked for any other unexplored child nodes, and so on.

For above graph depth first search will be 1->6->5->2->3->4

**Depth First Search Algorithm**

1. Start with a node S, and mark it as visited. 2. Current node u = S 3. While there is edge to be explored 3.1 Move to v where there is an edge (u,v). 3.2 If v is already not visited, mark v as visited 3.3 change u to v and repeat. 4. Move to parent of u.

Recursive implementation of above algorithm of depth first search on graph is very simple as shown below

1procedureDFS(G,v): 2 labelvas discovered 3for alledges fromvtowinG.adjacentEdges(v)do4ifvertexwis not labeled as discoveredthen5 recursively call DFS(G,w)

**Iterative implementation of depth first search**

1procedureDFS-iterative(G,v): 2 letSbe a stack 3S.push(v) 4whileSis not empty 5v=S.pop() 6ifvis not labeled as discovered: 7 labelvas discovered 8for alledges fromvtowinG.adjacentEdges(v)do9S.push(w)

Below figure explains how iterative depth first traversal works using stacks.

This implementation works only if graph has only one connected component. If graph has more than connected components, depth first search is done starting with each node. For more details on connected components, refer : connected components in graphs

Complexity of depth first search of graph is O(V+E) where V is number of vertices and E is number of edges.

**Applications of depth first search**

Minimum spanning tree

To check if graph has a cycle.

Topological sorting

To find strongly connected components of graph

To find bridges in graph

Pingback: Breadth First Search (BFS) on a graph – Algorithms and Me()

Pingback: Connected components in undirected graph - Algorithms and Me()