1. Introduction

Depth-First Search (DFS) is another fundamental graph traversal algorithm, which explores as far as possible along each branch before backtracking. Unlike BFS that uses a queue, DFS uses a stack (either explicit or implicit through recursion). In this blog post, we’ll demonstrate how to implement the DFS algorithm to traverse a graph using an adjacency list representation in Java.

2. Program Steps

1. Define the Graph class with a list of linked lists to represent the adjacency list.

2. Implement methods to add nodes, add edges, and perform DFS.

3. Test the DFS traversal using a main class.

3. Code Program

import java.util.LinkedList;

class Graph {
    private final int numVertices;
    private final LinkedList<Integer>[] adjacencyList;

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

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

    // A recursive function for DFS traversal
    private void DFSUtil(int vertex, boolean[] visited) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        for (int i : adjacencyList[vertex]) {
            if (!visited[i]) {
                DFSUtil(i, visited);
            }
        }
    }

    // Perform DFS and print nodes in DFS order
    public void DFS(int startVertex) {
        boolean[] visited = new boolean[numVertices];
        DFSUtil(startVertex, visited);
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(5);

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);

        System.out.print("Depth-First Search starting from vertex 0:");
        graph.DFS(0);
    }
}

Output:

Depth-First Search starting from vertex 0: 0 1 3 4 2

4. Step By Step Explanation

1. We initialize our Graph class containing an array of LinkedLists. This array stores the adjacency list for each vertex of the graph.

2. A constructor initializes the adjacency list for all vertices.

3. The addEdge method adds an edge between two vertices by adding each vertex to the adjacency list of the other.

4. The DFSUtil method is a recursive helper for our DFS traversal. Starting from a given vertex, it visits adjacent vertices that have not been visited yet. The method prints vertices as they are visited.

5. The DFS method initializes the visited array and calls DFSUtil to start the traversal.

6. In the main method, a sample graph is created, and a DFS traversal is initiated starting from vertex 0.

7. The output showcases the DFS traversal order of the nodes in the graph.