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:

  1. Start with the source node and mark it as visited.
  2. Explore one of the unvisited neighbors of the source node.
  3. If an unvisited neighbor is found, recursively apply steps 1 and 2 to it.
  4. If no unvisited neighbors are found, backtrack to the previous node and repeat step 2.
  5. 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.

  1. 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.

Comments

Popular Posts on Code Katha

Java Interview Questions for 10 Years Experience

Sql Interview Questions for 10 Years Experience

Spring Boot Interview Questions for 10 Years Experience

Visual Studio Code setup for Java and Spring with GitHub Copilot

Java interview questions - Must to know concepts

Spring Data JPA

Data Structures & Algorithms Tutorial with Coding Interview Questions

Java interview questions for 5 years experience

Elasticsearch Java Spring Boot