Depth-First Search (DFS) program in Java: A Step-by-Step Guide

Depth-First Search (DFS) is a fundamental graph traversal technique used to explore nodes and edges of a graph systematically. DFS goes as deep as possible along each branch before backtracking, making it useful for applications such as solving mazes, analyzing network structures, and more.

In this guide, we will:

Explain the DFS algorithm.
Illustrate DFS with a diagram.
Provide a detailed Java implementation.
Demonstrate DFS usage with examples.

Understanding Depth-First Search (DFS)

DFS Algorithm Steps

Start at the Source Vertex: Begin traversal from the source vertex.
Mark as Visited: Mark the source vertex as visited.
Explore Adjacent Vertices: For each adjacent (unvisited) vertex, recursively perform DFS.
Backtrack: When there are no more adjacent vertices to explore, backtrack to the previous vertex.

Key Points

Stack-Based Recursion: DFS can be implemented using recursion, which implicitly uses a stack.
Traversal Order: DFS explores the depth (i.e., child vertices) before breadth (i.e., sibling vertices).

DFS with a Diagram

Consider the following graph:

0 --- 1
|     |
4 --- 3
 \   /
   2

DFS Traversal Starting from Vertex 0:

Start at 0. Mark 0 as visited.
Move to 1 (adjacent to 0). Mark 1 as visited.
Move to 3 (adjacent to 1). Mark 3 as visited.
Move to 2 (adjacent to 3). Mark 2 as visited.
No more adjacent unvisited vertices for 2, backtrack to 3.
Backtrack to 1.
Backtrack to 0, and explore remaining adjacent vertex 4. Mark 4 as visited.

DFS Traversal Order: 0 → 1 → 3 → 2 → 4

DFS Traversal Diagram

Here’s a visual representation of the DFS traversal process:

Start at 0
0 → 1 → 3 → 2 → Backtrack
0 → 4

Visited:
0 → 1 → 3 → 2 → 4

Java Implementation of DFS

Graph Class

Use the previously defined Graph class with an adjacency list:

import java.util.*;

// Graph class using adjacency list representation
public class Graph {
    private int vertices; // Number of vertices
    private LinkedList<Integer>[] adjList; // Adjacency list

    // Constructor
    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    // Add edge to the graph
    public void addEdge(int src, int dest) {
        adjList[src].add(dest); // Add edge from src to dest
        adjList[dest].add(src); // Add edge from dest to src (for undirected graph)
    }

    // Print the adjacency list of the graph
    public void printGraph() {
        for (int i = 0; i < vertices; i++) {
            System.out.print("Vertex " + i + ": ");
            for (Integer vertex : adjList[i]) {
                System.out.print(vertex + " ");
            }
            System.out.println();
        }
    }

    // Getter for adjacency list (for use in algorithms)
    public LinkedList<Integer>[] getAdjList() {
        return adjList;
    }
}

DFS Class

Implement the DFS traversal logic in a separate class:

// Depth-First Search
public class DFS {
    private boolean[] visited; // Array to track visited vertices

    // Constructor to perform DFS from a start vertex
    public DFS(Graph graph, int startVertex) {
        visited = new boolean[graph.getAdjList().length];
        System.out.print("DFS Traversal starting from vertex " + startVertex + ": ");
        dfs(graph, startVertex);
        System.out.println();
    }

    // Recursive DFS function
    private void dfs(Graph graph, int vertex) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        for (int adjacentVertex : graph.getAdjList()[vertex]) {
            if (!visited[adjacentVertex]) {
                dfs(graph, adjacentVertex);
            }
        }
    }
}

Example Usage

Here’s a sample program demonstrating DFS traversal on a graph:

public class DFSExample {
    public static void main(String[] args) {
        // Create a graph with 5 vertices
        Graph graph = new Graph(5);

        // Add edges to the graph
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);

        // Print the graph's adjacency list
        System.out.println("Graph adjacency list:");
        graph.printGraph();

        // Perform DFS starting from vertex 0
        new DFS(graph, 0);
    }
}

Expected Output

Graph adjacency list:
Vertex 0: 1 4 
Vertex 1: 0 3 4 
Vertex 2: 3 
Vertex 3: 1 2 4 
Vertex 4: 0 1 3 

DFS Traversal starting from vertex 0: 0 1 3 2 4

This output shows the adjacency list of the graph and the order of vertices visited during DFS.

Conclusion

Depth-First Search (DFS) is a crucial graph traversal algorithm that explores as deep as possible along each path before backtracking. This guide provided a detailed implementation of DFS in Java using recursion and an adjacency list for graph representation. Understanding DFS enables you to solve various problems in graph theory, such as finding connected components, detecting cycles, and pathfinding.

Summary of Key Points

Graph Representation: Used an adjacency list for efficient graph representation.
DFS Algorithm: Explores vertices by depth, using recursion to manage the traversal stack.
Java Implementation: Included code for graph construction, DFS traversal, and example usage.

By mastering DFS and its implementation, you can efficiently traverse and analyze complex graph structures, a fundamental skill in computer science and algorithm design.

Tags: Graphs, DFS, Algorithms, Java Programming, Graph Traversal

This blog post covers the detailed implementation of DFS in Java, including explanations and a diagram for better understanding. If you need further clarifications or have additional questions, feel free to ask!