DFS

Explores nodes by going deep before backtracking

Introduction

Depth First Search (DFS) is a graph traversal algorithm that explores all adjacent vertices of a node one by one, diving deep into each vertex's reachable nodes before backtracking. Unlike trees, graphs may have cycles, so a visited array is used to prevent revisiting nodes. This ensures all nodes are processed efficiently without repetition.

How it Works?

1

Start from a Node

Call DFS with the starting node (the node where you want to begin the traversal).

2

Check if the Node is Visited

If the node is already visited (marked in the visited array), return immediately. This prevents revisiting the node.

3

Mark the Node as Visited

Mark the current node as visited in the visited array to avoid processing it again.

4

Process the Node

Perform any required operation on the node (e.g., print its value).

5

Explore Neighbors

  • Look at all nodes directly connected to the current node (its neighbors from the adjacency list).
  • For each neighbor, if it hasn’t been visited, recursively call DFS on that neighbor.
6

Repeat Until Done

The recursion ensures that the algorithm explores as deep as possible along a path before backtracking to explore other neighbors.

Carousel image 1
Carousel image 2
Carousel image 3
Carousel image 4
Carousel image 5
Carousel image 6
Carousel image 7

Implementation of DFS on Graph

//dfsongraph.cpp
#include<iostream>
#include<vector>
using namespace std;
void dfs(vector<vector<int>>&adjlist,vector<bool>&visited,int u){
visited[u]=1;
cout<<u<<" ";
for(int &v:adjlist[u]){
    if(!visited[v]){
        dfs(adjlist,visited,v);
    }
}
}
int main(){
  vector<vector<int>> adjlist = {
    {1, 3, 2},
    {0},     
    {0, 3}, 
    {0, 2, 4, 5},
    {3}, 
    {3}   
};
vector<bool>visited(adjlist.size(),0);
for(int i=0;i<adjlist.size();i++){
    if(!visited[i]){
        dfs(adjlist,visited,i);
    }
}
}

Time Complexity

The time complexity of Depth First Search (DFS) is typically O(V + E), where:

  • V is the number of vertices (nodes) in the graph.

  • E is the number of edges in the graph.

Why O(V + E)?

O(V): Each vertex is visited once. The algorithm marks each vertex as visited to avoid revisiting it.

O(E): Each edge is checked once, as the algorithm explores all neighboring vertices for every visited node.

Best Case

  • The DFS quickly finds the target node, so the traversal terminates early, without visiting all vertices and edges.

  • In the best-case scenario, we visit a small subset of nodes and edges, leading to a faster termination. However, in general, DFS’s worst-case complexity is still O(V + E) because it would potentially explore all nodes and edges.

  • Time Complexity: O(V+E)

Average Case

  • On average, DFS explores all vertices and edges in the graph. This happens when the graph is not sparse or highly structured (i.e., it's not too easy to find the target node early).

  • The average case for DFS still leads to visiting all nodes and edges, so it remains O(V+E).

  • Time Complexity: O(V+E)

Worst Case

  • The graph is fully explored, meaning all vertices and edges are visited.

  • O(V+E), because in the worst case, the algorithm will visit every vertex and every edge in the graph.

  • Time Complexity: O(V+E)

Space Complexity

Visited Array

  • To keep track of which vertices have been visited during the traversal.

  • Space Complexity: O(V), where V is the number of vertices.

Recursive Call Stack

  • Since DFS is often implemented using recursion, each recursive call adds a new frame to the call stack

  • Space Complexity: O(H), where H is the maximum depth of the recursion.