LeetCode Patterns Flashcards: Graphs, BFS, DFS, Topological Sort, Union Find

The two main representations are adjacency lists and adjacency matrices. An adjacency list stores a list of neighbors for each node, typically as a hash map from node to list of neighbors. It uses O of V plus E space and is efficient for sparse graphs, which is most interview problems. An adjacency matrix uses a two-dimensional array where entry at row i column j indicates an edge from i to j, using O of V squared space. Many problems provide edges as a list of pairs, which you convert to an adjacency list before processing.

DFS on a graph works the same as on trees, exploring as far as possible along each branch before backtracking. The critical difference is that graphs can have cycles, so you must track visited nodes to avoid infinite loops. Use a hash set of visited nodes and check before processing each neighbor. Mark a node as visited when you first encounter it, not when you finish processing it. DFS can be implemented recursively or iteratively with a stack. Time complexity is O of V plus E where V is vertices and E is edges.

BFS explores all neighbors at the current distance before moving to the next distance level, using a queue. Start by enqueuing the source node and marking it visited. While the queue is not empty, dequeue a node, process it, and enqueue all unvisited neighbors, marking them visited. BFS guarantees finding the shortest path in unweighted graphs because it discovers nodes in order of their distance from the source. Track distance by processing the queue level by level, counting levels. Time complexity is O of V plus E.

Topological sort produces a linear ordering of nodes in a directed acyclic graph, or DAG, such that for every directed edge from A to B, A appears before B. It is used for dependency resolution: course prerequisites, build systems, task scheduling, and compilation order. Two approaches exist. Kahn's algorithm uses BFS: start with nodes having zero incoming edges, remove them and reduce neighbors' incoming counts, repeating until empty. DFS-based approach adds nodes to the result in reverse postorder. If the result does not include all nodes, the graph has a cycle.

Treat the grid as a graph where each land cell connects to its adjacent land cells. Iterate through every cell. When an unvisited land cell is found, increment the island count and run DFS or BFS from that cell, marking all connected land cells as visited. This explores the entire island in one traversal. After the traversal, all cells belonging to that island are marked, so they will not be counted again. The total island count equals the number of times you initiate a new traversal. This runs in O of rows times columns time.

Union Find, also called Disjoint Set Union, maintains a collection of disjoint sets and supports two operations: find, which determines which set an element belongs to, and union, which merges two sets. With path compression in find and union by rank, both operations run in nearly O of one amortized time. Union Find efficiently solves connected component problems, cycle detection in undirected graphs, Kruskal's minimum spanning tree algorithm, and determining if two nodes are in the same group.

Use DFS with three-state coloring: white for unvisited, gray for currently in the recursion stack, and black for fully processed. Start DFS from each unvisited node, marking it gray. If during exploration you encounter a gray node, a cycle exists because you have found a back edge to an ancestor in the current path. When a node's DFS completes with no cycle found, mark it black. Black nodes are safe to skip entirely. This runs in O of V plus E time. The gray state distinguishes back edges that indicate cycles from cross edges to already-processed nodes that do not indicate cycles. ---