IV. Graph Traversal Patterns (DFS & BFS)

Pattern 1: DFS - Connected Components / Island Counting

Used to explore complete contiguous regions, count isolated clusters, or flood-fill bounded areas in grids and adjacency lists.

The Logic:

1. Iterate over every node or grid cell $(r, c)$.

2. When an unvisited land/component is found, increment your component counter and trigger a recursive DFS.

3. In the DFS function, mark the current cell as visited (or mutate it in-place, e.g., turn '1' to '0').

4. Recursively visit all valid 4-directional or adjacent neighbors that meet the traversal conditions.

   Time Complexity: $O(V + E)$ or $O(R \times C)$ for grids, as each node/cell is visited a constant number of times.

   Example Problems: 130. Surrounded Regions, 200. Number of Islands, 417. Pacific Atlantic Water Flow, 547. Number of Provinces, 695. Max Area of Island, 733. Flood Fill, 841. Keys and Rooms, 1020. Number of Enclaves, 1254. Number of Closed Islands, 1905. Count Sub Islands, 2101. Detonate the Maximum Bombs.

   
   

Pattern 2: BFS - Connected Components / Island Counting (Level-by-Level & Multi-Source)

Used to find unweighted shortest paths, coordinate simultaneous multi-source expansions, or propagate state layer-by-layer.

The Logic:

1. Initialize a queue. For multi-source problems, push all starting sources into the queue simultaneously with initial distance $0$.

2. Maintain a visited set or distance matrix to prevent reprocessing.

3. While the queue is non-empty, process nodes level-by-level (popping current queue size).

4. For each popped node, explore valid adjacent neighbors, mark them visited, and enqueue them.

   Time Complexity: $O(V + E)$ or $O(R \times C)$ for a grid.

   Example Problems: 542. 01 Matrix, 994. Rotting Oranges, 1091. Shortest Path in Binary Matrix.

Pattern 3: DFS - Cycle Detection (3-Color / State Tracking)

Used in directed graphs to detect cycles and determine node safety.

The Logic:

1. Track the state of each node using three colors: 0 (Unvisited), 1 (Visiting / Currently in recursion stack), and 2 (Visited / Completely safe).

2. For each node, start DFS: mark the node as 1 (Visiting).

3. Recurse through its neighbors. If a neighbor is currently 1, a back-edge exists, confirming a cycle.

4. Once all outbound edges from the current node are processed without finding a cycle, mark the node as 2 (Visited) and return false.

   Time Complexity: $O(V + E)$ time and $O(V)$ auxiliary space for recursion and state array.

   Example Problems: 207. Course Schedule, 210. Course Schedule II, 802. Find Eventual Safe States, 1059. All Paths from Source Lead to Destination.

Pattern 4: BFS - Topological Sort (Kahn's Algorithm)

Used to find a linear ordering of vertices in a Directed Acyclic Graph (DAG) or detect if a valid ordering is possible.

The Logic:

1. Compute the in-degree (number of incoming edges) for every vertex and build the adjacency list.

2. Push all vertices with an in-degree of 0 into a BFS queue.

3. While the queue is non-empty, pop a vertex, append it to the topological order, and decrement the in-degree of all its neighbors.

4. If a neighbor's in-degree reaches 0, push it to the queue.

5. If the resulting order contains fewer than $V$ vertices, the graph contains a cycle.

   Time Complexity: $O(V + E)$ time and $O(V + E)$ space.

   Example Problems: 210. Course Schedule II, 269. Alien Dictionary, 310. Minimum Height Trees, 444. Sequence Reconstruction, 1136. Parallel Courses, 1857. Largest Color Value in a Directed Graph, 2050. Parallel Courses III, 2115. Find All Possible Recipes from Given Supplies, 2392. Build a Matrix With Conditions.

Pattern 5: Deep Copy / Cloning

Used when duplicating complex recursive pointer structures (like graphs or linked lists with arbitrary references) without creating reference cycles or duplicate copies.

The Logic:

1. Use a Hash Map mapping original_node -> cloned_node.

2. Traverse the graph using DFS or BFS.

3. When visiting a node, check if it already exists in the map. If yes, return the cached clone.

4. If not, create a new node copy, insert it into the map immediately (to handle self-loops and cyclic references), and recursively clone all adjacent neighbors.

   Time Complexity: $O(V + E)$ time and $O(V)$ space for the hash map.

   Example Problems: 133. Clone Graph, 138. Copy List with Random Pointer, 1490. Clone N-ary Tree, 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance.

Pattern 6: Shortest Path (Dijkstra's Algorithm / Min-Heap BFS)

Used to find the single-source shortest path or optimal path in a weighted graph with non-negative edge weights.

The Logic:

1. Maintain a dist array initialized to infinity, setting dist[start] = 0.

2. Push (0, start) into a Min-Heap (priority queue ordered by current accumulated weight).

3. Pop (current_cost, u). If current_cost > dist[u], skip processing (stale entry).

4. For each neighbor v of u with edge weight w: if current_cost + w < dist[v], update dist[v] and push (dist[v], v) into the Min-Heap.

   Time Complexity: $O((V + E) \log V)$ time and $O(V + E)$ space.

   Example Problems: 743. Network Delay Time, 778. Swim in Rising Water, 1514. Path with Maximum Probability, 1631. Path With Minimum Effort, 1976. Number of Ways to Arrive at Destination, 2045. Second Minimum Time to Reach Destination, 2203. Minimum Weighted Subgraph With the Required Paths, 2290. Minimum Obstacle Removal to Reach Corner, 2577. Minimum Time to Visit a Cell In a Grid, 2812. Find the Safest Path in a Grid.

   
   

Pattern 7: Shortest Path with Constraints (Bellman-Ford / BFS with Step Tracking)

Used for graphs with negative weights or when finding the shortest path constrained to at most $K$ edges/stops.

The Logic:

1. Maintain an array dist tracking the shortest distance to each vertex.

2. For $K$ steps, maintain a snapshot copy of dist (to ensure path updates only use edges from the previous step limit).

3. Relax all edges $(u, v, w)$: if prev_dist[u] + w < dist[v], update dist[v].

4. Alternatively, use a BFS tracking state as (node, current_cost, stops) and prune branches exceeding the step limit or known cost.

   Time Complexity: $O(K \cdot E)$ or $O(V \cdot E)$ time and $O(V)$ space.

   Example Problems: 787. Cheapest Flights Within K Stops, 1129. Shortest Path with Alternating Colors.

Pattern 8: Disjoint Set Union (Union-Find)

Used to handle dynamic connectivity, merge clusters incrementally, and detect cycles in undirected graphs.

The Logic:

1. Maintain a parent array and a rank/size array.

2. Implement find(x) with path compression: recursively set parent[x] = find(parent[x]) so future queries run in near-constant time.

3. Implement union(x, y) with union by rank/size: find roots of x and y. If roots match, a cycle is detected. If distinct, attach the smaller tree under the root of the larger tree and decrement component count.

   Time Complexity: $O(V + E \cdot \alpha(V)) \approx O(V + E)$, where $\alpha$ is the Inverse Ackermann function.

   Example Problems: 200. Number of Islands, 261. Graph Valid Tree, 305. Number of Islands II, 323. Number of Connected Components in an Undirected Graph, 547. Number of Provinces, 684. Redundant Connection, 721. Accounts Merge, 737. Sentence Similarity II, 947. Most Stones Removed with Same Row or Column, 952. Largest Component Size by Common Factor, 959. Regions Cut By Slashes, 1101. The Earliest Moment When Everyone Become Friends.

   
   

Pattern 9: Strongly Connected Components (Kosaraju / Tarjan)

Used to partition a directed graph into maximal subgraphs where every vertex is reachable from every other vertex within the component.

The Logic:

1. Kosaraju's Algorithm:

   • Run DFS on the original graph, pushing vertices onto a stack based on their finish times.

   • Transpose the graph (reverse the direction of all edges).

   • Pop vertices from the stack; if unvisited in the transposed graph, run DFS from that vertex to extract an entire Strongly Connected Component.

2. Condense each SCC into a single super-node to transform the graph into a DAG.

   Time Complexity: $O(V + E)$ time and $O(V + E)$ space.

   Example Problems: 210. Course Schedule II, 547. Number of Provinces, 1192. Critical Connections in a Network, 2127. Maximum Employees to Be Invited to a Meeting.

Pattern 10: Pattern 27: Bridges & Articulation Points (Tarjan’s Low-Link Value Algorithm)

Used to identify critical edges (bridges) or critical vertices (articulation points) whose removal increases the number of connected components.

The Logic:

1. Perform DFS while maintaining two discovery arrays: discovery_time[u] and low[u] (the earliest discovered node reachable from u using at most one back-edge).

2. For each neighbor v of u (excluding parent):

   • If v is unvisited: recurse DFS, then update low[u] = min(low[u], low[v]). If low[v] > discovery_time[u], then edge $(u, v)$ is a bridge.

   • If v is already visited: update low[u] = min(low[u], discovery_time[v]).

     Time Complexity: $O(V + E)$ time and $O(V)$ space.

     Example Problems: 1192. Critical Connections in a Network, 2360. Longest Cycle in a Graph.

Pattern 11: Minimum Spanning Tree (Kruskal’s & Prim’s Algorithms)

Used to connect all vertices in an undirected, weighted graph with minimum total edge weight and no cycles.

The Logic:

1. Kruskal's Algorithm (Edge-Centric):

   • Sort all edges in ascending order of their weights.

   • Initialize a Union-Find (DSU) structure across all vertices.

   • Iterate through the sorted edges: if the endpoints of an edge belong to different components, union them and add the edge weight to the MST total. Stop when $V - 1$ edges are chosen.

2. Prim's Algorithm (Vertex-Centric):

   • Start from an arbitrary node, add all connected edges to a Min-Heap.

   • Greedily pop the minimum weight edge connecting an unvisited node, mark it visited, and push its outgoing edges into the Min-Heap.

     Time Complexity: $O(E \log E)$ or $O(E \log V)$ time.

     Example Problems: 1135. Connecting Cities With Minimum Cost, 1168. Optimize Water Distribution in a Village, 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree, 1584. Min Cost to Connect All Points.

Pattern 12: Bidirectional BFS

Used to drastically reduce the search space when finding the shortest transformation path between a known start node and target node.

The Logic:

1. Maintain two sets/queues: front_queue initialized with start, and back_queue initialized with target.

2. Maintain separate visited sets or distance maps for both directions.

3. In each step, expand the smaller of the two frontiers to minimize the branching factor ($O(b^{d/2})$ vs $O(b^d)$).

4. If a node expanded from one side has already been reached by the other side, the shortest path is found.

   Time Complexity: $O(b^{d/2})$, where $b$ is the branching factor and $d$ is the distance between start and target.

   Example Problems: 126. Word Ladder II, 127. Word Ladder, 815. Bus Routes.