Lesson 35Intermediate55 minAssessment-backed

Depth-First Search

Explore deeply for connectivity, components, cycle detection, graph cloning, and ordering signals.

What you will be able to do

Explain DFS as deep exploration with backtracking.

Implement recursive DFS in Java, Python, and JavaScript.

Use visited states to prevent cycles and repeated work.

Count connected components and reason about reachability.

Choose recursive or iterative DFS based on depth and stack constraints.

Depth-first search follows one relationship chain as far as it can, then backtracks. It is the right mental model for reachability, connected components, cycle detection, graph cloning, and dependency exploration.

Visited State Is Not Optional

Graphs can contain cycles. Without visited tracking, DFS can revisit the same node forever. For cycle detection in directed graphs, use multiple states: unvisited, visiting, and done.

DFS stack explores deeply then backtracks — DFS trades breadth layers for deep exploration and backtracking.

Scenario: Tenant Reachability Audit

A SaaS security team audits which resources a tenant can reach through group membership, roles, projects, and inherited policies. DFS answers reachability and component boundaries, but must not cross tenant boundaries or loop through cyclic inheritance.

Need	DFS technique	Production risk
Reach all linked resources	visited set	Cycles and duplicate work.
Detect dependency cycle	visiting/done states	False positives if state is wrong.
Count islands/components	start DFS from every unvisited node	Missing isolated vertices.
Very deep graph	iterative stack	Call-stack overflow.

Connected components in an undirected graph — Components are graph islands discovered by repeated DFS or BFS.

Same Pattern in Java, Python, and JavaScript

Counting connected components is a canonical DFS problem: each new unvisited start node discovers one island.

import java.util.*;

class Components {
    static int count(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        int components = 0;
        for (int node : graph.keySet()) {
            if (visited.add(node)) {
                components++;
                dfs(node, graph, visited);
            }
        }
        return components;
    }

    static void dfs(int node, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
        for (int next : graph.getOrDefault(node, List.of())) {
            if (visited.add(next)) dfs(next, graph, visited);
        }
    }
}

Assessment trap

Recursive DFS may fail on extremely deep graphs. Use an explicit stack when depth is user-controlled or operationally unbounded.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

Return the number of connected components in an undirected graph.
Given prerequisites, return whether all courses can be finished.
Clone an undirected graph with possible cycles.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Example	Brute-force approach	Stronger solution	Production notes
Security reachability	Follow references without tracking visited.	Use DFS with visited set and tenant boundary checks.	Cycles can cause infinite traversal or repeated side effects.
Course prerequisite cycle	Use one boolean visited value.	Use unvisited/visiting/done states for directed cycle detection.	A back edge to visiting means a cycle.
Connected components	Start from one node and stop.	Run DFS/BFS from every unvisited node.	Isolated vertices must count as components.

Solved modelInterview Question Solutions

Question 1: Count Connected Components

Return the number of connected components in an undirected graph. Start DFS from every unvisited vertex. Each start discovers one component.

import java.util.*;

class Components {
    static int count(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        int components = 0;
        for (int node : graph.keySet()) {
            if (visited.add(node)) {
                components++;
                dfs(node, graph, visited);
            }
        }
        return components;
    }

    static void dfs(int node, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
        for (int next : graph.getOrDefault(node, List.of())) {
            if (visited.add(next)) dfs(next, graph, visited);
        }
    }
}

Question 2: Course Schedule Cycle Detection

Given prerequisites, return whether all courses can be finished. Use directed DFS with three states. Seeing a visiting node again means a dependency cycle.

import java.util.*;
class CourseSchedule { static boolean canFinish(int n, int[][] pre) { List<List<Integer>> g = new ArrayList<>(); for(int i=0;i<n;i++) g.add(new ArrayList<>()); for(int[] e:pre) g.get(e[1]).add(e[0]); int[] state = new int[n]; for(int i=0;i<n;i++) if(!dfs(i,g,state)) return false; return true; } static boolean dfs(int node,List<List<Integer>> g,int[] state){ if(state[node]==1) return false; if(state[node]==2) return true; state[node]=1; for(int next:g.get(node)) if(!dfs(next,g,state)) return false; state[node]=2; return true; } }

Question 3: Clone Graph

Clone an undirected graph with possible cycles. Use DFS plus a map from original node to cloned node. The map prevents infinite recursion and preserves shared references.

import java.util.*;
class Node { int val; List<Node> neighbors = new ArrayList<>(); Node(int v){val=v;} }
class CloneGraph { Map<Node,Node> seen = new HashMap<>(); Node clone(Node node) { if (node == null) return null; if (seen.containsKey(node)) return seen.get(node); Node copy = new Node(node.val); seen.put(node, copy); for (Node next : node.neighbors) copy.neighbors.add(clone(next)); return copy; } }

Solved modelWorked Interview Answer

Count connected components in a graph. Start DFS from every unvisited node. Each new start discovers exactly one component because DFS marks every reachable node in that island.

import java.util.*;

class Components {
    static int count(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        int components = 0;
        for (int node : graph.keySet()) {
            if (visited.add(node)) {
                components++;
                dfs(node, graph, visited);
            }
        }
        return components;
    }

    static void dfs(int node, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
        for (int next : graph.getOrDefault(node, List.of())) {
            if (visited.add(next)) dfs(next, graph, visited);
        }
    }
}

Hands-on drillTry It Yourself

Practice task

Draw a dependency graph with a cycle A -> B -> C -> A. Label unvisited, visiting, and done states during DFS.

Failure patternsCommon Mistakes to Avoid

No visited set in cyclic graphs.
Using one visited state for directed cycle detection.
Ignoring isolated vertices.
Recursive DFS on unbounded depth.
Crossing tenant or permission boundaries during traversal.

Execution guardrailQuick-Start Checklist

Define traversal start nodes.
Use visited set for reachability/components.
Use visiting/done states for directed cycles.
Handle disconnected graphs.
Consider iterative stack for deep inputs.
State O(V + E).

Recall drillKnowledge Check

Question	Strong answer
What is DFS good for?	Deep reachability, components, cycles, and backtracking-style exploration.
Why use three states?	To distinguish current recursion path from fully processed nodes.
What is component count?	Number of disconnected graph islands.

VocabularyKey Terms

Term	Meaning
DFS	Depth-first traversal.
Backtracking	Returning after exploring a branch.
Component	A connected island in a graph.
Cycle	A path that returns to an earlier node.
Recursion stack	Active call path during recursive DFS.

Next practiceFurther Reading

Practice number of islands, course schedule, clone graph, and eventual safe states.
Compare recursive and iterative DFS.
Review topological sort after directed cycle detection.

Breadth-First Search

Shortest Path Basics