DFS of Graph

Time: O(V+E)

Space: O(V)

Intuition

DFS explores as deep as possible along each branch before backtracking. Use a stack (or recursion): visit a node, mark it, then recursively visit all unvisited neighbors.

Algorithm

1visited[src]=true. DFS(src).
2DFS(u): add u to result. For each neighbor v: if not visited: visited[v]=true. DFS(v).

Example Walkthrough

Input: Graph: 0â†’[1,2,3], 1â†’[4], 2â†’[], 3â†’[], 4â†’[]

1.DFS(0): visit 0. Go to 1: visit 1. Go to 4: visit 4. Backtrack. Go to 2: visit 2. Go to 3: visit 3.
2.Result: [0,1,4,2,3].

Output: [0,1,4,2,3]

Common Pitfalls

•Mark as visited BEFORE recursing â€” not after â€” to prevent revisiting in undirected graphs.

DFS of Graph.java

Java

// Approach: DFS using recursion or explicit stack. Mark visited nodes to avoid revisiting.
// Time: O(V+E) Space: O(V)
import java.util.*;

class Solution {
    // Function to return a list containing the DFS traversal of the graph.
    public ArrayList<Integer> dfs(ArrayList<ArrayList<Integer>> adj) {
        ArrayList<Integer> list = new ArrayList<>();
        boolean[] visit = new boolean[adj.size()];
        for (int i = 0; i < adj.size(); i++) {
            if (!visit[i])
                dfsUtil(adj, list, visit, i);
        }

        return list;
    }

    private void dfsUtil(ArrayList<ArrayList<Integer>> adj, ArrayList<Integer> list, boolean[] visit, int idx) {
        visit[idx] = true;
        list.add(idx);
        for (int i = 0; i < adj.get(idx).size(); i++) {
            int neighbour = adj.get(idx).get(i);
            if (visit[neighbour])
                continue;
            dfsUtil(adj, list, visit, neighbour);
        }
    }
}

Was this solution helpful?