Depth-First Search (DFS) in Graph

Welcome to our beginner's guide to Depth-First Search (DFS) in Graph Theory! DFS is another fundamental algorithm used to traverse or search through the nodes of a graph in a systematic manner. Let's explore this fascinating algorithm together!

What is Depth-First Search (DFS)?

Depth-First Search is an algorithm used to traverse or search through the nodes of a graph in a depthward motion. It starts at a specific node (often referred to as the "source" node) and explores as far as possible along each branch before backtracking.

Imagine you're exploring a maze again. DFS would explore as far as possible along one path before backtracking and exploring another path.

How does DFS Work?

DFS employs a simple strategy of exploring nodes as deeply as possible along each branch before backtracking. The algorithm proceeds as follows:

Start with the source node and mark it as visited.
Explore one of the unvisited neighbors of the source node.
If an unvisited neighbor is found, recursively apply steps 1 and 2 to it.
If no unvisited neighbors are found, backtrack to the previous node and repeat step 2.
Repeat steps 1-4 until all reachable nodes are visited.

Exploring Depth-First Search (DFS) with an Example

Depth-First Search (DFS) is a fundamental graph traversal technique. We'll demonstrate it using a simple graph structure:


       A
      / \
     B - C
    / \   \
   D - E - F

In this graph, we have the following connections:

A is linked to B and C.
B is linked to A, D, and E.
C is linked to A and F.
D is linked to B and E.
E is linked to B, D, and F.
F is linked to C and E.

We begin our DFS traversal from node A.

DFS Traversal Steps:

Note:When we call something recursively, it uses the stack for execution and backtracking.

Initiate at Node A (Starting Point):

Mark A as visited.


       A
      / \
     B - C
    / \   \
   D - E - F

Visited: [A],Recursion Stack: [A]
Explore unvisited adjacent nodes:

Move to B, mark as visited.


       A
      / \
     B - C
    / \   \
   D - E - F

Visited: [A, B], Stack: [A, B]
Continue exploring adjacent nodes:

Proceed to D, mark as visited.


       A
      / \
     B - C
    / \   \
   D - E - F

Visited: [A, B, D], Stack: [A, B, D]
Explore further adjacent nodes:

Visit E, mark as visited.


       A
      / \
     B - C
    / \   \
   D - E - F

Visited: [A, B, D, E], Stack: [A, B, D, E]
Continue exploration:

Go to F, mark as visited.


       A
      / \
     B - C
    / \   \
   D - E - F

Visited: [A, B, D, E, F], Stack: [A, B, D, E, F]

Visit C, mark as visited.


       A
      / \
     B - C
    / \   \
   D - E - F

Visited: [A, B, D, E, F, C], Stack: [A, B, D, E, F, C]

And at the end Stack: [A, B, D, E, F, C] get backtracked from recurssion.

Output: Nodes visited in DFS order: A, B, D, E, F, C

Time Complexity:

The time complexity of DFS is O(V + E), where V represents the number of vertices and E the number of edges in the graph.

Space Complexity:

The space complexity of DFS, in the worst-case scenario, is O(V), considering V as the number of vertices.

Implementing DFS in Code

Now, let's take a look at how we can implement Depth-First Search in code. We'll provide examples in several programming languages to help you get started:


package codeKatha;

import java.util.*;

public class DFS {
    public void depthFirstSearch(Graph graph, Node source) {
    
        Set<Node> visited = new HashSet<>();
        
        dfsHelper(source, visited, graph);
        
    }

    private void dfsHelper(Node node, Set<Node> visited, Graph graph) {
    
        visited.add(node);
        System.out.println(node);

        for (Node neighbor : graph.getNeighbors(node)) {
        
            if (!visited.contains(neighbor)) {
            
                dfsHelper(neighbor, visited, graph);
            }
        }
    }
}


#include <iostream>
#include <unordered_set>
#include "Graph.h"

void DFS(Node& node, std::unordered_set<Node>& visited, Graph& graph) {

    visited.insert(node);
    std::cout << node << std::endl;

    for (Node neighbor : graph.getNeighbors(node)) {
    
        if (visited.find(neighbor) == visited.end()) {
            DFS(neighbor, visited, graph);
        }
    }
}


class DFS:
    def depth_first_search(self, graph, node, visited):
        visited.add(node)
        print(node)

        for neighbor in graph.get_neighbors(node):
            if neighbor not in visited:
                self.depth_first_search(graph, neighbor, visited)


class DFS {
    depthFirstSearch(node, visited, graph) {
    
        visited.add(node);
        console.log(node);

        for (let neighbor of graph.getNeighbors(node)) {
        
            if (!visited.has(neighbor)) {
                this.depthFirstSearch(neighbor, visited, graph);
            }
        }
    }
}

Graph: Concept and Important Algorithms

1. Basics of Graph Data Structure

2. Breadth-First Search (BFS) in Graph

3. Depth-First Search (DFS) in Graph

4. Topological Sort in Graph

5. Union-Find Algorithm in Graph

6. Prim's Algorithm in Graph

7. Dijkstra's Algorithm in Graph

8. Kruskal's Algorithm in Graph

Congratulations! You've now learned the basics of Depth-First Search in graph theory. Feel free to experiment with the provided code examples and explore further applications of DFS in your projects.

Search On Code Katha

Code Katha