Graph Algorithms
Study Reference

Directed = one-way arrows · Undirected = bidirectional · Weighted = cost on edge.

• Adjacency matrix → O(V²) space; cell[i][j]=1 means i→j reachable.
• Adjacency list → O(V+E) space; default for almost every problem.
• ⭐ Graph = tree that CAN have loops. Same BFS/DFS/backtracking toolkit applies.
• doodle: 0→[1,2] 1→[2] 2→[0] (source node → linked list of neighbors)

Insight: start = the airport present as a key but never as a destination.

Time O(n) · Space O(n)

• build map dep→arr, and reverseMap arr→dep
• start = key in map NOT present as key in reverseMap
• walk: print start→next, then start=next, next=map[next]

doodle: LHR→DFW→JFK→LAX→DXB (chain, find the head)

Practice: LeetCode 332 — "Reconstruct Itinerary" [!] (LC variant needs lexical/Hierholzer; session version assumes unique linear chain)

Insight: plain traversal from src; if you ever pop dst, it's reachable.

Time O(V+E) · Space O(V)

• visited[] + queue (BFS) or recursion (DFS)
• on each dequeue, scan adjacency list; if neighbor==dst → true
• queue empties without hit → false

doodle: src ● → ○ → ○ → ◎dst

Practice: LeetCode 1971 — "Find if Path Exists in Graph"

Insight: a node already on the current recursion stack = back edge = cycle.

Time O(V+E) · Space O(V)

• two arrays: visited[] AND recStack[]
• enter node → recStack=true; if neighbor's recStack==true → cycle
• ⚠ before returning up, set recStack[node]=false (unwind)

doodle: 1→2→0→1 (1 reappears on stack)

Practice: LeetCode 207 — "Course Schedule"

Insight: after all-pairs shortest paths, dist[i][i]<0 ⇒ negative cycle.

Time O(V³) · Space O(V²)

• triple loop k,i,j: dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j])
• k = intermediate vertex
• scan diagonal; any dist[i][i]<0 → true

💡 Bellman-Ford alt = O(V·E); pick by density.

Practice: LeetCode 787 (Bellman-Ford) · GfG — "Detect Negative Cycle Floyd Warshall"

Insight: tree = connected AND no cycle. Cycle check must ignore the parent edge.

Time O(V+E) · Space O(V)

• DFS(node, parent); if neighbor visited AND neighbor≠parent → cycle
• ⚠ without parent, A–B looks like a cycle (undirected edge seen twice)
• after DFS, every node visited → connected

doodle: 1—0—2 (parent skips the back-edge)

Practice: LeetCode 261 — "Graph Valid Tree"

Insight: pass a shared time counter; ++ on entry (arrival), ++ on exit (departure).

Time O(V+E) · Space O(V)

• arrival[v]=++time; recurse; departure[v]=++time
• loop all nodes for disconnected components
• ⚠ if cycles: only set arrival if not already set

doodle: (v: in=3, out=10) nested intervals

Practice: GfG — "Arrival and Departure Time of Vertices in DFS"

Insight: print vertices in DECREASING departure time = valid topo order.

Time O(V+E) · Space O(V)

• DFS, store departure[time]=vertex
• ⭐ max departure = 2·(n−1); iterate that index down to 0
• print stored vertices high→low

doodle: U→V ⇒ U before V

Practice: LeetCode 210 — "Course Schedule II" · GfG "Topological Sort"

Insight: color each node; every neighbor must be the opposite color.

Time O(V+E) · Space O(V)

• color child = !color[parent] (boolean flip)
• if neighbor already same color → not bipartite
• 💡 3+ groups? swap boolean for int 0/1/2…

doodle: ●—○—●—○ (alternating)

Practice: LeetCode 785 — "Is Graph Bipartite?"

Insight: ⭐ use BFS not DFS — explore all edges from a node, track running max, carry visited-set per path.

Time O(V·E) [!] · Space O(V)

• queue holds (vertex, costSoFar, visitedSet)
• if cost>K → maxCost=max(maxCost,cost)
• push neighbor with cost+edgeWeight, copy of visitedSet

doodle: 0 —11→ 6 —9→ 7 … keep max

Practice: GfG — "Maximum cost path from source to destination greater than given cost"

Insight: run DFS from every vertex; if any run fails to reach all others → not SC.

Time O(V·(V+E)) · Space O(V)

• for each start: fresh visited[], DFS, check all true
• any false → return false
• 💡 Kosaraju does it in O(V+E) with 2 passes + transpose [+]

doodle: every v ⇄ every v

Practice: GfG — "Strongly Connected (check)" · LeetCode 1192 (Tarjan variant)

Insight: ⭐ edges are unweighted (one dice throw = one hop), so BFS gives min throws.

Time O(n) · Space O(n)

• queue of (cell, dist); from cell v try v+1…v+6
• move[j]!=-1 → jump to move[j] (ladder if >j, snake if <j)
• first time you pop cell n−1 → return its dist

doodle: 1→[2..7] BFS levels = throws

Practice: GfG — "Snake and Ladder Problem" · LeetCode 909 "Snakes and Ladders"

Insight: non-negative weights + shortest path → min-heap keyed on cumulative weight, always expand the cheapest node first.

Time O(E log V) · Space O(V)

• dist[]=∞, dist[src]=0; PQ ordered by node weight
• pop u; relax each edge: if dist[u]+w < dist[v] update + push
• ⚠ only for NON-negative weights

doodle: PQ pops smallest-dist node ↑

Practice: LeetCode 743 "Network Delay Time" · GfG "Dijkstra"

Insight: ⭐ "find ALL possible paths" ⇒ backtracking. Add node, recurse, then remove it.

Time O(2ⁿ·n) [+] · Space O(n)

• DFS(src, current); if src==dst → save copy of current
• for each neighbor: add, recurse, remove (undo)
• no visited[] needed — it's a DAG

doodle: 0→1→3 | 0→2→3 (branch & undo)

Practice: LeetCode 797 "All Paths From Source to Target"

Insight: ⭐ last vertex to start an unvisited DFS is the only candidate; verify with one more DFS.

Time O(V+E) · Space O(V)

• loop all v; if unvisited → DFS, set candidate=v
• ⚠ don't just check visited[] after — combined runs mislead
• 2nd DFS from candidate w/ FRESH visited; all seen → answer, else −1

doodle: last-started v → reaches all?

Practice: GfG — "Find a Mother Vertex in a Graph"

Nodes + edges, nonlinear. Three flavors: directed (arrows show flow), undirected (edge is bidirectional), weighted (each edge carries a cost).

Two representations:

• Adjacency matrix — V×V grid, cell[i][j]=1 if i→j is an edge. Simple, but O(V²) space; wasteful for large sparse graphs (10⁵ nodes → 10¹⁰ cells).
• Adjacency list — array of lists; index i holds every neighbor reachable from i. O(V+E) space. This is the default for essentially every problem below.

⭐ TRICK — the mental unlock: a graph is just a binary tree that's allowed to contain loops. Every technique already learned (BFS, DFS, backtracking, hashmaps, auxiliary/visited arrays) transfers directly. The only structural difference: trees can't have cycles, graphs can. Don't treat "graph" as a scary new topic.

💡 TIP: the entire difficulty of a graph problem usually collapses to one decision — which traversal, and what extra state do I carry? (visited, recursion-stack, color, cost, parent, time). Identify that state and the code writes itself.

Why this matters: representation choice drives complexity. Matrix gives O(1) edge lookup but O(V²) space and O(V) neighbor scans; list gives O(degree) neighbor scans and O(V+E) space. Pick list unless you need constant-time edge existence checks on a dense graph.

Restatement: given (departure, arrival) airport pairs forming one linear route with no cycle and each airport visited once, print the itinerary in order.

Practice: LeetCode 332 — "Reconstruct Itinerary". [!] The LeetCode version allows multiple tickets from one airport and demands lexical order via Hierholzer's algorithm (Eulerian path). The version here assumes a strict one-in/one-out chain, so the simple hashmap walk below solves that simpler problem, not the harder LC one. For the chain version, search GfG — "Find the itinerary from a given list of tickets".

Pattern / family: hashmap key–value chaining; "find the head of a linked structure."

Approach — the whole game is finding the start.

• Build map: departure → arrival (this is the given input as a map).
• Build reverseMap: arrival → departure.
• ⭐ TRICK: the overall starting airport is the one that appears as a key in map but never appears as a key in reverseMap (i.e., it's a source but never a destination). Everything else has something pointing into it.
• From that start, repeatedly print start → map[start], then advance start = map[start] until no mapping exists.

Complexity: O(n) time, O(n) space (n = number of airports).

// Session version: unique linear chain, one ticket per airport.
static void printItinerary(Map<String,String> dataset) {
    // reverseMap: destination -> source
    Map<String,String> reverseMap = new HashMap<>();
    for (Map.Entry<String,String> e : dataset.entrySet()) reverseMap.put(e.getValue(), e.getKey());

    // start = a source that is never a destination
    String start = null;
    for (Map.Entry<String,String> e : dataset.entrySet()) {
        if (!reverseMap.containsKey(e.getKey())) { start = e.getKey(); break; }
    }
    if (start == null) return; // invalid / cyclic input

    String to = dataset.get(start);
    while (to != null) {
        System.out.println(start + " -> " + to);
        start = to;
        to = dataset.get(to);
    }
}

⚠ PITFALL: don't try to sort or use a priority queue — this isn't value-sorting, it's dependency ordering. The only "sort" is following the chain from its unique head.

Interview follow-ups: what if an airport has multiple outgoing tickets? → becomes an Eulerian-path problem (Hierholzer). What if the route has a cycle? → no unique head exists; the start == null branch flags invalid input.

Why this matters: "find the element that appears on one side but not the other" is a reusable hashmap idiom (course prerequisites, dependency roots, linked-list heads).

Restatement: given a directed graph and two vertices src, dst, determine whether dst is reachable from src (and optionally print the path).

Practice: LeetCode 1971 — "Find if Path Exists in Graph".

Pattern / family: plain graph traversal. Either BFS (queue) or DFS (recursion/stack) works — both correct here.

Approach: start at src, mark visited, explore neighbors via the adjacency list. The moment you encounter dst, return true. If the traversal completes without hitting dst, return false.

Complexity: O(V+E) time, O(V) space.

class Graph {
    int V;
    LinkedList<Integer>[] adj;

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) adj[i] = new LinkedList<>();
    }
    void addEdge(int u, int w) { adj[u].add(w); }

    boolean isReachable(int s, int d) {
        boolean[] visited = new boolean[V];
        Queue<Integer> q = new LinkedList<>();
        visited[s] = true;
        q.add(s);
        while (!q.isEmpty()) {
            int n = q.poll();
            for (int next : adj[n]) {          // iterate neighbors
                if (next == d) return true;    // reached destination
                if (!visited[next]) {
                    visited[next] = true;
                    q.add(next);
                }
            }
        }
        return false;
    }
}

💡 TIP — BFS vs DFS template note: the outer loop (queue non-empty) plus inner loop (iterate neighbors) mirrors the binary-tree BFS template exactly. The only new thing in graphs is iterating the adjacency list instead of left/right children.

⚠ PITFALL: forgetting the visited[] array. In a graph with cycles, omitting it causes infinite loops (this is the concrete cost of "graphs can have loops").

Interview follow-ups: print the actual path → carry a parent[] map and backtrack from dst; count shortest hops → BFS level count.

Why this matters: reachability is the skeleton under connectivity, path-existence, and flood-fill problems.

Restatement: given a directed graph, return true if it contains a cycle.

Practice: LeetCode 207 — "Course Schedule" (cycle detection = can't finish courses). Also GfG — "Detect Cycle in a Directed Graph".

Pattern / family: DFS with two markers.

Brute idea → why it fails: a single visited[] array can't distinguish "seen earlier in a different branch" from "seen on the current path." You need path-awareness.

⭐ TRICK — the recursion stack: keep a second array recStack[] that marks nodes currently on the active DFS path. If DFS reaches a node whose recStack is already true, that's a back edge → cycle. Example: path 1→2→0, then edge 0→1 — node 1 is still on the stack, so revisiting it proves a cycle.

⚠ PITFALL — you must unwind: when DFS finishes a node and returns to its parent, set recStack[node]=false. The node leaves the current path even though visited stays true. Forgetting this reports false cycles. (This is exactly the backtracking "reverse the operation before returning" step.)

Complexity: O(V+E) time, O(V) space.

class Graph {
    int V;
    List<List<Integer>> adj;

    Graph(int v) {
        V = v;
        adj = new ArrayList<>();
        for (int i = 0; i < v; i++) adj.add(new ArrayList<>());
    }
    void addEdge(int src, int dst) { adj.get(src).add(dst); }

    boolean cyclicUtil(int i, boolean[] visited, boolean[] recStack) {
        if (recStack[i]) return true;       // already on current path -> cycle
        if (visited[i])  return false;      // fully processed elsewhere, no cycle

        visited[i]  = true;
        recStack[i] = true;                 // enter path

        for (int child : adj.get(i)) if (cyclicUtil(child, visited, recStack)) return true;

        recStack[i] = false;                // UNWIND: leave path before returning
        return false;
    }

    boolean isCyclic() {
        boolean[] visited  = new boolean[V];
        boolean[] recStack = new boolean[V];
        for (int i = 0; i < V; i++) if (cyclicUtil(i, visited, recStack)) return true;
        return false;
    }
}

💡 TIP: intuition for DFS-over-BFS here — a cycle is discovered by diving deep and coming back to a node still in the call stack. BFS explores level by level and doesn't naturally expose the "still on my current path" relationship.

Interview follow-ups: undirected graph cycle detection uses parent-tracking instead of a recursion stack (see Problem 5). Course Schedule II asks for the topo order (Problem 7).

Why this matters: the visited + recursion-stack pair is the canonical directed-cycle test and underpins deadlock detection and build-dependency validation.

Restatement: given a weighted directed graph, determine whether any cycle has a negative total weight.

Practice: LeetCode 787 — "Cheapest Flights Within K Stops" (Bellman-Ford practice). For the exact task, GfG — "Detect a negative cycle in a graph (Floyd Warshall)" and GfG — "Detect Negative Cycle Bellman Ford".

Pattern / family: all-pairs shortest path (Floyd-Warshall); alternatively single-source Bellman-Ford.

⭐ TRICK: compute all-pairs shortest distances, then inspect the diagonal. If any dist[i][i] < 0, a vertex can reach itself with negative total cost → a negative cycle exists. Because we always minimize, a genuine negative loop drives the self-distance below zero.

Approach — Floyd-Warshall: three nested loops. k is an intermediate vertex; i is source; j is destination. For every triple, relax: if going i→k→j is shorter than the current i→j, update it.

Complexity: O(V³) time, O(V²) space. [!] One learner guessed O(V·E) — that's Bellman-Ford's bound, not Floyd-Warshall's. F-W is strictly O(V³).

static final int INF = 1_000_000_000;

static boolean hasNegativeCycle(int[][] graph, int V) {
    int[][] dist = new int[V][V];
    for (int i = 0; i < V; i++) dist[i] = graph[i].clone();     // init with given weights

    for (int k = 0; k < V; k++)                 // intermediate vertex
    for (int i = 0; i < V; i++)             // source
    for (int j = 0; j < V; j++)         // destination
    if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];

    for (int i = 0; i < V; i++) if (dist[i][i] < 0) return true;         // self-distance negative
    return false;
}

💡 TIP — Bellman-Ford alternative: relax every edge V−1 times using dist[u] + weight(u,v) < dist[v]; then do one more pass — if any edge still relaxes, there's a negative cycle. Cost O(V·E). Choose by density: few edges → Bellman-Ford (V·E small); dense/near-complete graph → Floyd-Warshall's V³ can win, and it also gives you all-pairs distances for free.

⚠ PITFALL: guard the relaxation against INF overflow — adding two INF sentinels can wrap. The != INF checks above prevent phantom short paths.

Interview follow-ups: another to know is Johnson's algorithm (reweighting + Dijkstra) for sparse all-pairs; treat it as "standard, memorize if needed."

Why this matters: negative-cycle detection matters in arbitrage, currency conversion, and any shortest-path system where edges can be negative.

Restatement: return true if a given undirected graph is a tree — i.e., it is connected and has no cycle.

Practice: LeetCode 261 — "Graph Valid Tree".

Pattern / family: undirected cycle detection via DFS, plus a connectivity check.

Approach: DFS from node 0. Detect a cycle; if none exists AND every node was visited (connected), it's a tree.

⚠ PITFALL — the whole trap of this problem: in an undirected graph, edge A–B appears in both A's and B's adjacency lists. Naively, after going A→B, DFS sees B→A and thinks "A is already visited → cycle!" — a false positive. ⭐ TRICK: pass the parent into the recursion. A visited neighbor only signals a real cycle if it is NOT the parent you just came from.

Complexity: O(V+E) time, O(V) space.

class Graph {
    int V;
    List<List<Integer>> adj;

    boolean cyclicUtil(int v, boolean[] visited, int parent) {
        visited[v] = true;
        for (int nbr : adj.get(v)) {
            if (!visited[nbr]) {
                if (cyclicUtil(nbr, visited, v)) return true;  // pass v as parent
            } else if (nbr != parent) {
                return true;                 // visited & not parent => real cycle
            }
        }
        return false;
    }

    boolean isTree() {
        boolean[] visited = new boolean[V];
        if (cyclicUtil(0, visited, -1)) return false;   // cycle => not a tree
        for (int i = 0; i < V; i++) if (!visited[i]) return false;              // disconnected => not a tree
        return true;
    }
}

💡 TIP: the framing — this is the same DFS as directed cycle detection, but because the graph is undirected you swap the recursion-stack for parent-tracking. Interviewers deliberately switch "directed" vs "undirected" in the prompt to see if you notice; read the graph type first.

Interview follow-ups: alternative tree test — a connected undirected graph is a tree iff it has exactly V−1 edges. Union-Find also solves this cleanly.

Why this matters: parent-tracking generalizes to any undirected cycle problem (redundant connection, minimum spanning tree edge validation).

Restatement: compute, for each vertex, its arrival time (first explored) and departure time (all neighbors done, about to backtrack).

Practice: GfG — "Arrival and Departure Time of Vertices in DFS".

Pattern / family: DFS with a shared, monotonically increasing timestamp — the base technique that powers topological sort and articulation-point algorithms.

Approach: maintain one global time. On entering vertex v, arrival[v] = ++time. Recurse into unvisited neighbors. Before returning, departure[v] = ++time. Loop over all vertices so disconnected components are covered.

Complexity: O(V+E) time, O(V) space.

class Graph {
    int V;
    List<List<Integer>> adj;

    // time passed & returned so it stays shared across the whole DFS
    int dfs(int v, boolean[] discovered, int[] arrival, int[] departure, int time) {
        arrival[v] = ++time;         // prefix increment = arrival stamp
        discovered[v] = true;
        for (int u : adj.get(v)) if (!discovered[u]) time = dfs(u, discovered, arrival, departure, time);
        departure[v] = ++time;       // stamp on the way out
        return time;
    }

    void computeTimes() {
        int[] arrival = new int[V], departure = new int[V];
        boolean[] discovered = new boolean[V];
        int time = -1;               // so first ++time == 0
        for (int i = 0; i < V; i++) if (!discovered[i]) time = dfs(i, discovered, arrival, departure, time);
    }
}

⭐ TRICK — init time = -1: using prefix ++time everywhere means the very first stamp is -1+1 = 0. Clean zero-based timestamps with no special-casing.

⚠ PITFALL — cycles: if the graph can contain cycles, add a guard so you only set arrival[v] when it hasn't been set yet; don't overwrite the start time of an already-visited node. (This caveat is easy to miss when a cycle is present.)

💡 TIP: the time counter is passed as a parameter and returned — that's what keeps it shared/consistent across sibling recursive calls without a class field. Recognize "shared counter through recursion" as its own mini-pattern.

Why this matters: arrival/departure intervals are the foundation for topological sort, cycle classification (tree/back/forward/cross edges), and Tarjan's SCC/bridge algorithms.

Restatement: given a DAG, output a linear ordering where for every edge U→V, U appears before V. Any valid ordering is acceptable.

Practice: LeetCode 210 — "Course Schedule II". Also GfG — "Topological Sort".

Pattern / family: direct application of DFS departure times (Problem 6).

⭐ TRICK — the core realization: print vertices in decreasing order of departure time and you get a valid topological order. No separate sorting pass, no priority queue.

Storage trick: store departure[time] = vertex (time as index, vertex as value) so you can walk the array from high time to low and directly read off vertices. You want to print vertices, not times, so this inversion is deliberate.

⭐ Bound insight: for n vertices the maximum possible departure time is 2·(n−1) (each vertex contributes an arrival and a departure stamp; n=8 → max stamp 15). Size the departure array to 2·n and iterate that index downward.

Complexity: O(V+E) time, O(V) space.

class Graph {
    int V;
    List<List<Integer>> adj;

    int dfs(int v, boolean[] discovered, int[] departure, int time) {
        discovered[v] = true;
        time++;
        for (int u : adj.get(v)) if (!discovered[u]) time = dfs(u, discovered, departure, time);
        departure[time] = v;   // time = index, vertex = value
        time++;
        return time;
    }

    void topologicalSort() {
        int[] departure = new int[2 * V];
        Arrays.fill(departure, -1);
        boolean[] discovered = new boolean[V];
        int time = 0;
        for (int i = 0; i < V; i++) if (!discovered[i]) time = dfs(i, discovered, departure, time);

        // print in DECREASING departure time
        for (int t = 2 * V - 1; t >= 0; t--) if (departure[t] != -1) System.out.print(departure[t] + " ");
    }
}

💡 TIP: this graph is NOT weighted, yet departure times still exist — a learner asked exactly this. Departure time is a DFS byproduct, independent of edge weights. Same technique as the unweighted arrival/departure problem.

⚠ PITFALL: topological sort is only defined on a DAG. If the graph has a cycle there is no valid ordering — pair this with cycle detection (Problem 3) if the input isn't guaranteed acyclic.

Interview follow-ups: Kahn's algorithm (BFS with in-degrees) is the common alternative and naturally detects cycles (if fewer than V nodes are emitted, a cycle exists).

Why this matters: build systems, task scheduling, course prerequisites, and dependency resolution all reduce to topological sort.

Restatement: determine whether an undirected graph's vertices can be split into two disjoint sets U and V such that every edge connects a vertex in U to one in V.

Practice: LeetCode 785 — "Is Graph Bipartite?".

Pattern / family: graph coloring via DFS.

⭐ TRICK: assign each vertex a boolean color. When you recurse to a neighbor, give it the OPPOSITE color: color[neighbor] = !color[current]. If you ever reach a neighbor already colored the SAME as the current node, an edge connects two same-set vertices → not bipartite.

Why boolean: exactly two sets, so true/false is enough. Think "team A has the light on, team B has it off."

Complexity: O(V+E) time, O(V) space.

class Graph {
    int V;
    List<List<Integer>> adj;

    boolean dfs(int v, boolean[] discovered, boolean[] color) {
        for (int u : adj.get(v)) {
            if (!discovered[u]) {
                discovered[u] = true;
                color[u] = !color[v];               // opposite color
                if (!dfs(u, discovered, color)) return false;
            } else if (color[u] == color[v]) {
                return false;                        // same color across an edge
            }
        }
        return true;
    }

    boolean isBipartite() {
        boolean[] discovered = new boolean[V];
        boolean[] color = new boolean[V];
        int src = 0;
        discovered[src] = true;
        color[src] = false;
        return dfs(src, discovered, color);
    }
}

💡 TIP — extending to k groups: a learner asked "what if a third team joins?" Boolean can't hold 3 states. Swap it for an int color array using 0/1/2… The coloring logic is otherwise identical. (This is the natural bridge to the general graph-coloring / m-coloring problem.)

⚠ PITFALL: the code as written assumes a connected graph (single DFS from src). For a graph with multiple components, wrap the DFS in a loop over all undiscovered vertices — otherwise you silently ignore uncolored components.

Interview follow-ups: bipartite ⇔ no odd-length cycle. BFS-coloring is an equally valid implementation.

Why this matters: bipartite testing underlies matching problems (jobs↔applicants), conflict/scheduling graphs, and two-team partitioning.

Restatement: in a weighted graph, find the maximum-cost path from a source to any other vertex whose total cost exceeds a given K; the path must not contain a cycle. Weights may be negative.

Practice: GfG — "Maximum cost path from source to destination greater than given cost". (No direct LeetCode equivalent.)

Pattern / family: BFS carrying rich per-path state (running cost + visited set).

⭐ TRICK — why BFS, not DFS (the key point): at each node you want to consider ALL outgoing edges and track the best running cost, rather than committing to one deep dive. That "stay at the current node, fan out over every edge, keep the max" behavior is BFS. DFS commits to diving deep before it has compared alternatives. Negative weights make greedy/early-cutoff wrong, so you must explore all edge options — BFS with state does this cleanly.

Approach: the queue holds a triple — (current vertex, cost accumulated so far, set of vertices visited on this path). On each pop: if cost > K, update the global max. Then for every outgoing edge to an unvisited (per this path) vertex, push the neighbor with cost + edgeWeight and a copied visited-set (to forbid cycles).

Complexity: often quoted as O(V·E). [!] That figure is misleading; because this enumerates acyclic paths it is exponential in the worst case (path enumeration), not truly O(V·E). Trust O(V·E) only as the per-relaxation framing, not a tight bound. Space O(V) per queued state.

class State {
    int vertex, cost;
    Set<Integer> visited;
    State(int v, int c, Set<Integer> vis) { vertex = v; cost = c; visited = vis; }
}

int findMaxCost(List<int[]>[] adj, int src, int K) {
    Queue<State> q = new LinkedList<>();
    Set<Integer> start = new HashSet<>();
    start.add(src);
    q.add(new State(src, 0, start));

    int maxCost = Integer.MIN_VALUE;
    while (!q.isEmpty()) {
        State cur = q.poll();
        if (cur.cost > K) maxCost = Math.max(maxCost, cur.cost);

        for (int[] edge : adj[cur.vertex]) {   // edge = {destination, weight}
            int dest = edge[0], w = edge[1];
            if (!cur.visited.contains(dest)) {  // no cycle on this path
                Set<Integer> nextVis = new HashSet<>(cur.visited);
                nextVis.add(dest);
                q.add(new State(dest, cur.cost + w, nextVis));
            }
        }
    }
    return maxCost;
}

💡 TIP — the walkthrough: trace it: from 0 pick the 11-edge over the 5-edge; from 6 pick the 9-edge, etc. — always comparing all edges out of the current node and keeping the max running total. That comparison-at-each-node is precisely the BFS advantage here.

⚠ PITFALL: the visited set must be COPIED per branch, not shared. A single global visited set would forbid a vertex on paths that never actually contained it. Copying is what makes "no cycle on this path" correct.

Interview follow-ups: for the shortest-path mirror (minimum cost), the same BFS-with-state skeleton applies but you track the min; on graphs without negative weights, Dijkstra is the specialized tool.

Why this matters: "BFS carrying path state" generalizes to constrained-path problems (max/min cost with forbidden revisits, path-with-budget, k-stop routing).

Restatement: a directed graph is strongly connected if every vertex is reachable from every other vertex. Return true/false.

Practice: GfG — "Check if a graph is strongly connected (Set 1, Kosaraju)". LeetCode 1192 — "Critical Connections in a Network" is the closest Tarjan-flavored practice.

Pattern / family: repeated DFS reachability.

Approach (session's brute-but-clear method): for each vertex as a start, run a fresh DFS with a new visited[]. If any starting vertex fails to reach all others (some visited[i] stays false), the graph is not strongly connected. Only if every start reaches everything is it strongly connected.

Complexity: O(V·(V+E)) time, O(V) space — one full traversal per vertex.

class Graph {
    int V;
    List<List<Integer>> adj;

    void dfs(int v, boolean[] visited) {
        visited[v] = true;
        for (int u : adj.get(v)) if (!visited[u]) dfs(u, visited);
    }

    boolean isStronglyConnected() {
        for (int start = 0; start < V; start++) {
            boolean[] visited = new boolean[V];   // fresh per start
            dfs(start, visited);
            for (boolean seen : visited) if (!seen) return false;          // couldn't reach some vertex
        }
        return true;
    }
}

💡 TIP — the linear alternative (Kosaraju) [+]: the approach above is the O(V·(V+E)) brute force. Kosaraju does it in O(V+E): (1) DFS the graph once; if any vertex is unreachable from a chosen start, it's not SC. (2) Transpose all edges. (3) DFS the transpose from the same start; if all reachable, the graph is strongly connected. Tarjan's SCC algorithm is the other standard linear method.

⚠ PITFALL: reset the visited[] array for every starting vertex — reusing a stale array across starts gives wrong answers. (Re-initialize inside the loop.)

⚠ Note [!]: despite any name overlap, this is a strong-connectivity check, not a bipartiteness check — the logic described is strong-connectivity.

Interview follow-ups: if the interviewer wants optimal, reach for Kosaraju or Tarjan; the interviewer mainly wants to see you arrive at a correct approach, and DFS-based reachability is the honest starting point.

Why this matters: strong connectivity underlies deadlock analysis, web-page reachability, and condensation of graphs into SCC DAGs.

Restatement: on a board where some cells have ladders (jump up) or snakes (slide down), find the minimum number of dice throws to reach the last cell from the first. The player controls the dice outcome (1–6).

Practice: LeetCode 909 — "Snakes and Ladders". Also GfG — "Snake and Ladder Problem".

Pattern / family: shortest path on an unweighted graph → BFS. Each cell is a node; from cell v you have edges to v+1…v+6.

⭐ TRICK — why BFS, not Dijkstra: every dice throw costs exactly one move regardless of where you land. Uniform edge weight is the signature of BFS. Because BFS explores in expanding "rings" of equal distance, the first time you reach the destination cell you've reached it in the fewest throws. (Same reasoning as shortest path in an unweighted matrix.)

⭐ TRICK — snake/ladder as one mapping array: use a single move[] array. move[i] = -1 means an ordinary cell. Otherwise move[i] is the destination: if move[i] > i it's a ladder, if move[i] < i it's a snake. When you land on such a cell, you go straight to move[i] with no extra throw.

Complexity: O(n) time, O(n) space (n = number of cells).

static class QEntry { int v, dist; QEntry(int v, int d){ this.v=v; this.dist=d; } }

static int getMinDiceThrows(int[] move, int n) {
    boolean[] visited = new boolean[n];
    Queue<QEntry> q = new LinkedList<>();
    visited[0] = true;
    q.add(new QEntry(0, 0));            // start cell, distance 0

    QEntry cur = null;
    while (!q.isEmpty()) {
        cur = q.poll();
        int v = cur.v;
        if (v == n - 1) break;          // reached last cell
        for (int j = v + 1; j <= v + 6 && j < n; j++) {  // dice 1..6, in bounds
            if (!visited[j]) {
                visited[j] = true;
                int dest = (move[j] != -1) ? move[j] : j; // ladder/snake or stay
                q.add(new QEntry(dest, cur.dist + 1));
            }
        }
    }
    return cur.dist;
}

⚠ PITFALL: the j < n guard in the inner loop is essential — near the end of the board, v+6 can overshoot and cause index-out-of-bounds. Also mark cells visited when you enqueue (as above), not when you dequeue, to avoid duplicate queue entries.

💡 TIP: this is a very common interview question. The exact board changes but the technique is fixed — recognize "minimum moves, uniform cost, jump-cells" and reach for BFS with a mapping array.

Interview follow-ups: if dice weights varied, it'd become Dijkstra (Problem 12); if you needed the actual sequence of throws, carry a parent pointer and backtrack.

Why this matters: "model cells/states as graph nodes, edges as legal moves, BFS for fewest moves" transfers to word-ladder, minimum-knight-moves, and puzzle-state problems.

Restatement: given a weighted graph with all non-negative edge weights and a source vertex, find the shortest-path distance from the source to every other vertex.

Practice: LeetCode 743 — "Network Delay Time". Also GfG — "Dijkstra's shortest path algorithm".

Pattern / family: greedy shortest path using a min-heap (priority queue).

⭐ TRICK — decision rule: shortest path + weights present + all weights non-negative → Dijkstra. (Contrast: no weights → BFS, as in Problem 11; negative weights possible → Bellman-Ford / Floyd-Warshall, Problem 4.)

Approach: maintain dist[] initialized to ∞ (except source = 0). Push (source, 0) into a min-heap whose comparator orders by node weight (cumulative distance). Repeatedly pop the smallest-distance node u; for each edge u→v with weight w, relax: if dist[u] + w < dist[v], update dist[v], record prev[v]=u, and push (v, dist[v]). Mark u done so it isn't reprocessed.

⭐ Why the min-heap: the heap's root is always the unfinished vertex with the currently smallest tentative distance — exactly the one Dijkstra must finalize next. The weight is used as the heap comparator; the heapify does the "pick smallest" work for you automatically.

Complexity: O(E log V) time, O(V) space.

class Node { int vertex, weight; Node(int v, int w){ vertex=v; weight=w; } }
class Edge { int src, dest, weight; /* ctor */ }

void shortestPath(List<List<Edge>> adj, int source, int n) {
    // min-heap ordered by cumulative weight
    PriorityQueue<Node> minHeap = new PriorityQueue<>((a, b) -> a.weight - b.weight);
    minHeap.add(new Node(source, 0));

    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;

    boolean[] done = new boolean[n];
    int[] prev = new int[n];
    prev[source] = -1;

    while (!minHeap.isEmpty()) {
        int u = minHeap.poll().vertex;
        if (done[u]) continue;              // skip stale heap entries
        for (Edge e : adj.get(u)) {
            int v = e.dest, w = e.weight;
            if (!done[v] && dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;      // relax
                prev[v] = u;
                minHeap.add(new Node(v, dist[v]));
            }
        }
        done[u] = true;                     // finalized, never picked again
    }
    // dist[i] now holds shortest distance source -> i; prev[] rebuilds routes
}

⚠ PITFALL — never use Dijkstra with negative edges. The greedy "finalize the smallest and never revisit" step breaks when a later negative edge could have improved a finalized node. For negative weights use Bellman-Ford or Floyd-Warshall (Problem 4).

💡 TIP: frame the whole algorithm as "min-heap property + weight as comparator; everything else is the heapify you already learned." If you're comfortable with heaps, Dijkstra is mostly bookkeeping (dist[], prev[], done[]).

Interview follow-ups: print the actual route via the prev[] array (recurse from a node back through predecessors); a lazy-deletion heap (the done[u] skip above) avoids needing a decrease-key operation.

Why this matters: Dijkstra underlies routing/navigation, network latency (Network Delay Time), and any non-negative weighted shortest-path task; it also appears inside larger system-design answers (e.g., nearest-locker / nearest-driver).

Restatement: given a DAG with nodes labeled 0…n−1 (as an adjacency list), return every possible path from node 0 to node n−1, in any order.

Practice: LeetCode 797 — "All Paths From Source to Target".

Pattern / family: DFS with backtracking (enumerate all solutions).

⭐ TRICK — the trigger phrase: "find all possible paths" is the classic signal for backtracking. You explore one choice deeply, record a complete path when you hit the target, then undo the last choice and try the next. DFS is the natural traversal; backtracking is the add/recurse/remove discipline layered on top.

Approach: keep a current path list seeded with the source. In DFS: if the current node equals the destination (n−1), add a copy of current to the answer. Otherwise, for each neighbor: add it to current, recurse, then remove it (the backtracking undo).

Complexity: O(2ⁿ · n) worst case [+] — a DAG can have exponentially many source-to-target paths, and copying each path costs O(n). (No tight bound is stated above; this is the standard figure.) Space O(n) for the recursion depth plus current path.

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    List<List<Integer>> answer = new ArrayList<>();
    List<Integer> current = new ArrayList<>();
    current.add(0);                        // start at source 0
    dfs(0, current, graph, graph.length - 1, answer);
    return answer;
}

void dfs(int src, List<Integer> current, int[][] graph, int dest, List<List<Integer>> answer) {
    if (src == dest) {                     // reached target
        answer.add(new ArrayList<>(current)); // add a COPY
        return;
    }
    for (int next : graph[src]) {
        current.add(next);                 // choose
        dfs(next, current, graph, dest, answer);
        current.remove(current.size() - 1); // un-choose (backtrack)
    }
}

⚠ PITFALL — add a COPY, not the reference. answer.add(new ArrayList<>(current)) is required; adding current directly stores a live reference that later backtracking will mutate, corrupting every saved path.

💡 TIP — no visited[] needed here. Because the input is a DAG (acyclic), you can't loop, so you don't need a visited array to prevent cycles. The remove step alone restores state between branches. (If the graph could contain cycles, you'd add per-path cycle protection.)

Interview follow-ups: this exact pattern showed up in an interview as the "Mario reaches the destination — find all paths" matrix problem; the grid version adds 4-directional moves and treats walls as blockers (an extra boundary condition that returns early). A follow-up "find the minimum path" switches the tool from backtracking-DFS to BFS.

Why this matters: add / recurse / remove is the universal backtracking skeleton — it powers permutations, subsets, combinations, N-Queens, and path-enumeration alike.

Restatement: a mother vertex is a vertex from which every other vertex in the graph is reachable. Find one (or report none exists).

Practice: GfG — "Find a Mother Vertex in a Graph".

Pattern / family: DFS traversal + a single verification pass (a lightweight version of Kosaraju's finishing-order idea).

Approach — two phases:

• Phase 1 (find candidate): loop over all vertices with one shared visited[]. Whenever you hit an unvisited vertex, DFS from it and record it as the current candidate. The last vertex that triggers a DFS is your only possible mother vertex.
• Phase 2 (verify): run a fresh DFS from that candidate using a new visited array. If it reaches every vertex, return the candidate; otherwise return −1 (no mother vertex).

⚠ PITFALL — the central gotcha the whole session circled: after Phase 1 you cannot just check "is every entry in visited[] true?". That array can be fully true because combined DFS runs from several start vertices covered everything — that does NOT mean any single vertex reached all others. You must re-verify with a fresh DFS from the one candidate. (Example: with edge 5→6 removed, vertex 5 reaches only 2 while vertex 6 reaches the rest; the shared array is all-true but neither alone is a mother vertex.)

⭐ TRICK — why the last unvisited-start is the candidate: if a mother vertex exists, it must be able to reach every other vertex, so its own DFS (if started) would finish last in the loop — any vertex processed after it would have to be unreachable from it, contradicting "mother." Hence only the final starting vertex can qualify, which is why one verification pass suffices instead of V full checks.

Complexity: O(V+E) time, O(V) space.

static void dfsUtil(List<List<Integer>> g, int v, boolean[] visited) {
    visited[v] = true;
    for (int u : g.get(v)) if (!visited[u]) dfsUtil(g, u, visited);
}

static int findMotherVertex(List<List<Integer>> g, int V) {
    boolean[] visited = new boolean[V];
    int candidate = -1;

    // Phase 1: last vertex to start a fresh DFS is the candidate
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            dfsUtil(g, i, visited);
            candidate = i;
        }
    }

    // Phase 2: verify candidate reaches everything (FRESH array)
    boolean[] check = new boolean[V];
    dfsUtil(g, candidate, check);
    for (boolean seen : check) if (!seen) return -1;      // some vertex unreachable -> no mother vertex
    return candidate;
}

💡 TIP: if two mother vertices exist (e.g., a mutual edge makes both reach everything), returning any one is acceptable — the problem asks for a mother vertex, not all of them.

Interview follow-ups: the rigorous version uses Kosaraju's finishing-time stack (the last-finished vertex in the first DFS pass is the candidate); the two-phase method above is the intuitive equivalent.

Why this matters: the "candidate from traversal order, then verify" structure recurs in SCC detection and in problems where one pass narrows the search and a second confirms it.

Meta-pattern: almost everything is DFS with one extra piece of carried state — recursion-stack (3), parent (5), timestamp (6,7), color (8), path+undo (13) — while BFS wins when you must compare all edges from a node or measure hops under uniform cost (2, 9, 11). Weighted shortest path splits by sign: non-negative → Dijkstra's min-heap (12), negative-possible → Floyd-Warshall/Bellman-Ford (4). *Row 9's O(V·E) is a commonly quoted figure and row 13's O(2ⁿ·n) is the standard bound; both are path-enumeration exponential in the worst case.