Depth First Search ( DFS ) Algorithm
Key points
- DFS is an algorithm for traversing a Graph or a Tree.
- DFS starts with the root node and explores all the nodes along the depth of the selected path before backtracking to explore the next path.
- DFS makes use of Stack for storing the visited nodes of the graph / tree.
Example: Consider the below step-by-step DFS traversal of the tree. If the source is root ( node 0 ), the nodes 2 & 4 along the depth of the tree are explored before the other nodes in the tree.
Algorithm : Depth first search (Graph G, Souce_Vertex S) 1. Create a stack STK to store the vertices. 2. Push the source vertex S in the stack STK. 3. While the stack STK is not empty 4. Pop the vertex U from the top of the stack. i.e Vertex U = STK.top(), STK.pop() 5. If the vertex U is not visited, Then 6. Explore the vertex U and mark U as visited. 7. For every vertex V adjacent to vertex U 8. Push the vertex V in the stack STK
Example of depth-first search traversal on a graph : In the below unweighted graph, the DFS algorithm beings by exploring node ‘0’, followed by its adjacent vertex node ‘1’, followed by its adjacent vertex node ‘3’ and so on.
Example of depth-first search traversal on a tree : In the below tree, the DFS algorithm beings by exploring node ‘0’ followed by its adjacent vertex node ‘1’, followed by node ‘2’ then node ‘3’ before backtracking to explore the next path.
Data structure used for storing graph or tree : Adjacency List
Data structure used for depth first search : Stack
Time complexity of depth first search : O ( V + E ) for an adjacency list implementation of a graph or a tree. ‘V’ is the number of vertices and ‘E’ is the number of edges in a graph/tree.Why is the time complexity of depth first search algorithm O ( V + E ) : When the graph is stored in an adjacency list, the neighbors of a vertex on the out going edge are explored successively/linearly. As each vertex is explored only once, all the vertices are explored in O ( V ) time. The total number of edges (maintained in the adjacency list) are 2*E (bi-directional) for an undirected graph and E for a directed graph. Thus the time complexity is O ( 2.E + V ) for an undirected graph and O ( E + V ) for a directed graph.
Depth First Search Implementation
from collections import deque
from collections import defaultdict
class Graph:
def __init__(self, nodes : int) :
# Store the adjacency list as a dictionary
# { 0 : [ 1, 2 ], 1 : [ 3, 4 ] }
# The default dictionary would create an empty list as a default (value)
# for the nonexistent keys.
self.adjlist = defaultdict(list)
self.nodes = nodes
self.visited = [False] * nodes
def AddEdge (self, src : int, dst : int) :
self.adjlist[src].append(dst)
self.adjlist[dst].append(src)
# Recursive version of DFS
def DFS (self, src : int) :
self.visited[src] = True
print(src, end = ' ')
if src in self.adjlist : # Check if the key (src) exists in the dictionary (adjlist)
for adj_node in self.adjlist[src] :
if self.visited[adj_node] == False :
self.DFS(adj_node)
# Iterative version of DFS
def DFSIterative (self, src : int) :
stack = deque()
stack.append(src)
while stack :
src = stack.popleft()
if self.visited[src] == False :
self.visited[src] = True
print(src, end = ' ')
if src in self.adjlist :
for adj_node in self.adjlist[src] :
stack.appendleft(adj_node)
def MarkUnvisited (self) :
# Reset the visited array for next iteration of breadth first search
self.visited = [False] * self.nodes
def main():
nodes = 7
g = Graph(nodes)
g.AddEdge(0, 1)
g.AddEdge(0, 2)
g.AddEdge(1, 3)
g.AddEdge(1, 4)
g.AddEdge(2, 3)
g.AddEdge(3, 5)
g.AddEdge(4, 6)
g.AddEdge(5, 6)
print("\nDFS Graph Traversal Recursive")
print("Source Node 0 :", end = " ")
g.DFS(0)
g.MarkUnvisited()
print("\nSource Node 3 :", end = " ")
g.DFS(3)
g.MarkUnvisited()
print("\n\nDFS Graph Traversal Iterative")
print("Source Node 0 :", end = " ")
g.DFSIterative(0)
g.MarkUnvisited()
print("\nSource Node 3 :", end = " ")
g.DFSIterative(3)
nodes = 10
t = Graph(nodes)
t.AddEdge(0,1)
t.AddEdge(0,6)
t.AddEdge(0,7)
t.AddEdge(1,2)
t.AddEdge(1,4)
t.AddEdge(1,5)
t.AddEdge(2,3)
t.AddEdge(7,8)
t.AddEdge(7,9)
print("\n\nDFS Tree Traversal")
print("Root Node (0): ", end = " ")
t.DFS(0)
t.MarkUnvisited()
print("\nRoot Node (4): ", end = " ")
t.DFS(4)
t.MarkUnvisited()
print("\n\nDFS Tree Traversal Iterative")
print("Source Node 0 :", end = " ")
t.DFSIterative(0)
t.MarkUnvisited()
print("\nSource Node 4 :", end = " ")
t.DFSIterative(4)
if __name__ == "__main__" :
main()
Output
DFS Graph Traversal Recursive
Source Node 0 : 0 1 3 2 5 6 4
Source Node 3 : 3 1 0 2 4 6 5
DFS Graph Traversal Iterative
Source Node 0 : 0 2 3 5 6 4 1
Source Node 3 : 3 5 6 4 1 0 2
DFS Tree Traversal
Root Node (0): 0 1 2 3 4 5 6 7 8 9
Root Node (4): 4 1 0 6 7 8 9 2 3 5
DFS Tree Traversal Iterative
Source Node 0 : 0 7 9 8 6 1 5 4 2 3
Source Node 4 : 4 1 5 2 3 0 7 9 8 6
#include<iostream>
#include<list>
#include<vector>
#include<stack>
using namespace std;
class Graph {
private:
int nodes;
list<int> *adjlist;
vector<bool> visited;
public:
Graph() {
}
Graph (int nodes) { // Allocate resources
adjlist = new list<int> [nodes];
visited.resize(nodes, false);
this->nodes = nodes;
}
~Graph () { // Free allocated resources
delete [] adjlist;
}
void AddEdge (int src, int dst) {
adjlist[src].push_back(dst);
adjlist[dst].push_back(src);
}
// DFS recursive
void DFS (int src) {
visited[src] = true;
cout << src << " ";
for (auto& adj_node : adjlist[src]) {
if (!visited[adj_node]) {
DFS(adj_node);
}
}
}
// DFS iterative
void DFS_Iterative (int src) {
stack<int> stk;
visited[src] = true;
stk.push(src);
while (!stk.empty()) {
src = stk.top();
stk.pop();
cout << src << " ";
for (auto &adj_node : adjlist[src]) {
if (!visited[adj_node]) {
visited[adj_node] = true;
stk.push(adj_node);
}
}
}
}
// Mark nodes unvisited for next traversal
void MarkUnvisited () {
fill(visited.begin(), visited.end(), false);
}
};
int main()
{
Graph g(7);
g.AddEdge(0,1);
g.AddEdge(0,2);
g.AddEdge(1,3);
g.AddEdge(1,4);
g.AddEdge(2,3);
g.AddEdge(3,5);
g.AddEdge(4,6);
g.AddEdge(5,6);
cout << "DFS Recursive Graph Traversal " << endl;
cout << "Source Node (0): "; g.DFS(0);
g.MarkUnvisited(); cout << endl;
cout << "Source Node (3): "; g.DFS(3);
g.MarkUnvisited(); cout << endl;
cout << "DFS Iterative Graph Traversal" << endl;
cout << "Source Node (0): "; g.DFS_Iterative(0);
g.MarkUnvisited(); cout << endl;
cout << "Source Node (3): "; g.DFS_Iterative(3);
g.MarkUnvisited(); cout << endl << endl;
Graph t(10);
t.AddEdge(0,1);
t.AddEdge(0,6);
t.AddEdge(0,7);
t.AddEdge(1,2);
t.AddEdge(1,4);
t.AddEdge(1,5);
t.AddEdge(2,3);
t.AddEdge(7,8);
t.AddEdge(7,9);
cout << "DFS Recursive Tree Traversal" << endl;
cout << "Root Node (0): "; t.DFS(0);
t.MarkUnvisited(); cout << endl;
cout << "Root Node (4): "; t.DFS(4);
t.MarkUnvisited(); cout << endl;
cout << "DFS Iterative Tree Traversal" << endl;
cout << "Source Node (0): "; t.DFS_Iterative(0);
t.MarkUnvisited(); cout << endl;
cout << "Source Node (4): "; t.DFS_Iterative(4);
t.MarkUnvisited(); cout << endl;
return 0;
}
Output
DFS Recursive Graph Traversal
Source Node (0): 0 1 3 2 5 6 4
Source Node (3): 3 1 0 2 4 6 5
DFS Iterative Graph Traversal
Source Node (0): 0 2 3 5 6 4 1
Source Node (3): 3 5 6 4 2 0 1
DFS Recursive Tree Traversal
Root Node (0): 0 1 2 3 4 5 6 7 8 9
Root Node (4): 4 1 0 6 7 8 9 2 3 5
DFS Iterative Tree Traversal
Source Node (0): 0 7 9 8 6 1 5 4 2 3
Source Node (4): 4 1 5 2 3 0 7 9 8 6
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;
import java.util.Arrays;
class DFSTraversal {
static class Graph {
Integer nodes;
List<List<Integer>> adjlist;
boolean[] visited;
Graph (int arg_nodes) {
nodes = arg_nodes;
adjlist = new ArrayList<>(nodes);
for (int i=0; i<nodes; i++)
adjlist.add(new ArrayList<>());
visited = new boolean[nodes];
}
void AddEdge (int src, int dst) {
adjlist.get(src).add(dst);
adjlist.get(dst).add(src);
}
// DFS recursive implementation
void DFS (int src) {
visited[src] = true;
System.out.print(src + " ");
for (int adj_node : adjlist.get(src)) {
if (!visited[adj_node]) {
DFS(adj_node);
}
}
}
// DFS iterative implementation
void DFS_Iterative (int src) {
Stack<Integer> stk = new Stack<>();
stk.push(src);
while (!stk.empty()) {
src = stk.peek();
stk.pop();
if (!visited[src]) {
visited[src] = true;
System.out.print(src + " ");
for (int adj_node : adjlist.get(src)) {
stk.push(adj_node);
}
}
}
}
// Mark nodes unvisited for next traversal
void MarkUnvisited () {
Arrays.fill(visited, false);
}
}
public static void main (String[] args) {
Graph g = new Graph(7);
g.AddEdge(0,1);
g.AddEdge(0,2);
g.AddEdge(1,3);
g.AddEdge(1,4);
g.AddEdge(2,3);
g.AddEdge(3,5);
g.AddEdge(4,6);
g.AddEdge(5,6);
System.out.println("DFS Recursive Graph Traversal ");
System.out.print("\nSource Node (0): "); g.DFS(0);
g.MarkUnvisited();
System.out.print("\nSource Node (3): "); g.DFS(3);
g.MarkUnvisited();
System.out.println("\n\nDFS Iterative Graph Traversal");
System.out.print("\nSource Node (0): "); g.DFS_Iterative(0);
g.MarkUnvisited();
System.out.print("\nSource Node (3): "); g.DFS_Iterative(3);
g.MarkUnvisited();
Graph t = new Graph(10);
t.AddEdge(0,1);
t.AddEdge(0,6);
t.AddEdge(0,7);
t.AddEdge(1,2);
t.AddEdge(1,4);
t.AddEdge(1,5);
t.AddEdge(2,3);
t.AddEdge(7,8);
t.AddEdge(7,9);
System.out.println("\n\nDFS Recursive Tree Traversal");
System.out.print("\nRoot Node (0): "); t.DFS(0);
t.MarkUnvisited();
System.out.print("\nRoot Node (4): "); t.DFS(4);
t.MarkUnvisited();
System.out.println("\n\nDFS Iterative Tree Traversal");
System.out.print("\nSource Node (0): "); t.DFS_Iterative(0);
t.MarkUnvisited();
System.out.print("\nSource Node (4): "); t.DFS_Iterative(4);
t.MarkUnvisited();
}
}
Output
DFS Recursive Graph Traversal
Source Node (0): 0 1 3 2 5 6 4
Source Node (3): 3 1 0 2 4 6 5
DFS Iterative Graph Traversal
Source Node (0): 0 2 3 5 6 4 1
Source Node (3): 3 5 6 4 1 0 2
DFS Recursive Tree Traversal
Root Node (0): 0 1 2 3 4 5 6 7 8 9
Root Node (4): 4 1 0 6 7 8 9 2 3 5
DFS Iterative Tree Traversal
Source Node (0): 0 7 9 8 6 1 5 4 2 3
Source Node (4): 4 1 5 2 3 0 7 9 8 6