Implement DFS Algo

Problem Statement

Given a graph represented as an adjacency list and a starting vertex, perform a Depth-First Search (DFS) traversal and return the order in which vertices are visited.

Example:

• Input: V = 5, Edges = [[0,1],[0,2],[1,3],[2,4]], start = 0
• Output: [0, 1, 3, 2, 4]

Noob-Friendly Explanation

Imagine you're in a maze. DFS means you pick one path and keep going as deep as possible until you hit a dead end. Then you backtrack and try the next path. It's like exploring a cave — you go all the way down one tunnel before coming back to try another.

You can do this using recursion (the function calls itself) or a stack (last-in-first-out, like a stack of plates).

Approach 1: Brute Force (Using Adjacency Matrix)

Intuition

Store the graph in an adjacency matrix. For each vertex, scan the entire row to find unvisited neighbors and recursively visit them.

Algorithm

1. Create a V×V adjacency matrix from the edges.
2. Start DFS from the given vertex.
3. Mark the vertex as visited, print it.
4. Scan the entire row to find neighbors and recursively visit unvisited ones.

public class DFSBruteForce {
    static void dfs(int[][] matrix, boolean[] visited, int node, int V) {
        visited[node] = true;
        System.out.print(node + " ");

        // Scan entire row — O(V) per vertex
        for (int i = 0; i < V; i++) {
            if (matrix[node][i] == 1 && !visited[i]) {
                dfs(matrix, visited, i, V);
            }
        }
    }

    public static void main(String[] args) {
        int V = 5;
        int[][] edges = {{0,1},{0,2},{1,3},{2,4}};

        int[][] matrix = new int[V][V];
        for (int[] edge : edges) {
            matrix[edge[0]][edge[1]] = 1;
            matrix[edge[1]][edge[0]] = 1;
        }

        boolean[] visited = new boolean[V];
        dfs(matrix, visited, 0, V); // Output: 0 1 3 2 4
    }
}

Complexity Analysis

• Time Complexity: O(V^2) — for each vertex we scan an entire row of V elements.
• Space Complexity: O(V^2) — for the adjacency matrix.

Approach 2: Optimal (Using Adjacency List)

Intuition

Use an adjacency list so we only visit actual neighbors. Use recursion to go as deep as possible before backtracking.

Algorithm

1. Build an adjacency list from the edges.
2. Create a visited array.
3. Call the recursive DFS function from the start vertex.
4. In the DFS function, mark the vertex visited, add to result, and recurse for all unvisited neighbors.

import java.util.ArrayList;
import java.util.List;

public class DFSOptimal {
    static void dfs(List<List<Integer>> adj, boolean[] visited, int node, List<Integer> result) {
        visited[node] = true;
        result.add(node);

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                dfs(adj, visited, neighbor, result);
            }
        }
    }

    public static void main(String[] args) {
        int V = 5;
        int[][] edges = {{0,1},{0,2},{1,3},{2,4}};

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        boolean[] visited = new boolean[V];
        List<Integer> result = new ArrayList<>();
        dfs(adj, visited, 0, result);
        System.out.println(result); // [0, 1, 3, 2, 4]
    }
}

Complexity Analysis

• Time Complexity: O(V + E) — each vertex and edge is visited exactly once.
• Space Complexity: O(V) — for the visited array and recursion stack.