DFS

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?

Start from a Node

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

Check if the Node is Visited

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

Mark the Node as Visited

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

Process the Node

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

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.

Repeat Until Done

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

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);
    }
}
}

# dfs_on_graph.py

def dfs(adjlist, visited, node):
 """
 Performs DFS traversal on a graph using adjacency list
 """
 visited[node] = True
 print(node, end=" ")
 
 # Visit all unvisited neighbors recursively
 for neighbor in adjlist[node]:
     if not visited[neighbor]:
         dfs(adjlist, visited, neighbor)

def dfs_complete_graph(adjlist):
 """
 Performs DFS on all components of the graph
 """
 visited = [False] * len(adjlist)
 result = []
 
 for i in range(len(adjlist)):
     if not visited[i]:
         component_start = len([x for x in visited if x])  # Count visited nodes
         dfs(adjlist, visited, i)
         print()  # New line after each component

# Example usage
if __name__ == "__main__":
 # Adjacency list representation
 adjlist = [
     [1, 3, 2],    # Node 0 connected to 1, 3, 2
     [0],          # Node 1 connected to 0
     [0, 3],       # Node 2 connected to 0, 3
     [0, 2, 4, 5], # Node 3 connected to 0, 2, 4, 5
     [3],          # Node 4 connected to 3
     [3]           # Node 5 connected to 3
 ]
 
 print("DFS Traversal of the graph:")
 dfs_complete_graph(adjlist)

# Alternative: DFS from a specific starting node
def dfs_from_node(adjlist, start):
 visited = [False] * len(adjlist)
 print(f"DFS starting from node {start}:")
 dfs(adjlist, visited, start)
 print()

# Example: Start DFS from node 0
# dfs_from_node(adjlist, 0)
# Output: 0 1 3 2 4 5

// dfs_on_graph.js

function dfs(adjList, visited, node) {
 /**
  * Performs DFS traversal on a graph using adjacency list
  */
 visited[node] = true;
 process.stdout.write(node + " ");
 
 // Visit all unvisited neighbors recursively
 for (const neighbor of adjList[node]) {
     if (!visited[neighbor]) {
         dfs(adjList, visited, neighbor);
     }
 }
}

function dfsCompleteGraph(adjList) {
 /**
  * Performs DFS on all components of the graph
  */
 const visited = new Array(adjList.length).fill(false);
 
 for (let i = 0; i < adjList.length; i++) {
     if (!visited[i]) {
         dfs(adjList, visited, i);
         console.log(); // New line after each component
     }
 }
}

// Example usage
function main() {
 // Adjacency list representation
 const adjList = [
     [1, 3, 2],     // Node 0 connected to 1, 3, 2
     [0],           // Node 1 connected to 0
     [0, 3],        // Node 2 connected to 0, 3
     [0, 2, 4, 5],  // Node 3 connected to 0, 2, 4, 5
     [3],           // Node 4 connected to 3
     [3]            // Node 5 connected to 3
 ];
 
 console.log("DFS Traversal of the graph:");
 dfsCompleteGraph(adjList);
}

// Alternative: DFS from a specific starting node
function dfsFromNode(adjList, start) {
 const visited = new Array(adjList.length).fill(false);
 console.log(`DFS starting from node ${start}:`);
 dfs(adjList, visited, start);
 console.log();
}

main();

// Example: Start DFS from node 0
// dfsFromNode(adjList, 0);
// Output: 0 1 3 2 4 5

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.

DFS

On this page