Graphs

A social network is a graph, a road map is a graph, an `import` graph in your codebase is a graph, and so is the dependency tree of a package manager. The reason graphs feel everywhere is that they are the most general relationship structure: just vertices and edges, with no required root, no acyclic constraint, and no fixed branching factor. **Graphs: Representation Basics** is where you stop drawing them on whiteboards and start storing them in code. This lesson defines the core vocabulary (vertex, edge, degree, path, cycle, directed and undirected, connected and disconnected) and walks through the three canonical representations: an adjacency list backed by a hash map of vertex to neighbors, an adjacency matrix for dense graphs and `O(1)` edge-existence queries, and an edge list for algorithms that just iterate over edges. You will analyze the space and time trade-offs of each so you can pick the right one before writing any traversal logic. In **Hash Map (Dictionary) Basics**, you saw that a hash map maps keys to values in expected `O(1)`; an adjacency list is exactly that, mapping each vertex to its list of neighbors. **Queue & Deque** gave you the FIFO machinery that BFS will run on top of these representations once traversal lessons begin. With a graph stored in memory, the algorithms track is where it comes alive: BFS, DFS, shortest paths, connected components, and the rest of the graph algorithm canon.

Given a million pairwise 'these two accounts belong to the same person' relations, decide whether two arbitrary accounts are now equivalent. Brute-force flood fills are `O(n)` per query; sorting is the wrong shape entirely. **Union-Find** answers each query in nearly `O(1)` amortized time after the relations are merged, with two primitives and a parent array. This lesson covers the disjoint-set abstraction, the `find` operation that walks parent pointers up to a representative, the `union` operation that links two representatives, and the two optimizations (path compression during `find` and union by rank during `union`) that together push the amortized cost to `O(alpha(n))`, where `alpha` is the inverse Ackermann function (effectively constant for any input you can fit in memory). You will trace the parent array as merges happen, and apply the structure to cycle detection in undirected graphs, connected components, equivalence classes, and Kruskal's minimum spanning tree. In **Arrays & Strings**, you saw that an array can encode a mapping from index to value in `O(1)`; a parent array is exactly that mapping, applied to representative pointers. **Graphs: Representation Basics** gave you the vertex-and-edge vocabulary that Union-Find uses to define connectivity, even though the structure itself stores no edges directly. With Union-Find in your toolkit, the curriculum continues with composite designs that combine multiple primitives, starting with the LRU cache pattern.

Highways have lengths in kilometers, flights have ticket prices in dollars, and network links have latencies in milliseconds. Treating any of those graphs as unweighted throws away the only information that matters for the question you actually care about (the shortest, cheapest, or fastest route), which is exactly the gap a **Weighted Graph** representation closes by attaching a number to every edge. This lesson covers three representations: a weighted adjacency list backed by arrays of `{node, weight}` pairs, a weighted adjacency matrix where `matrix[u][v]` is the edge cost (and infinity for non-edges), and a weighted edge list that stores `(u, v, weight)` triples. You will analyze the space and time trade-offs, see why Dijkstra wants the adjacency list, why Floyd-Warshall wants the matrix, and why Kruskal wants the edge list, and you will represent both directed and undirected weighted graphs correctly in each format. In **Graphs: Representation Basics**, you stored connectivity (whether an edge exists) using the same three shapes; the weighted version simply replaces a boolean or membership check with a numeric value. **Hash Map (Dictionary) Basics** is what makes the adjacency list work: a vertex maps to its neighbor-and-weight list in expected `O(1)`, the same way the unweighted version did. With weights in the picture, the algorithms track unlocks shortest-path and minimum-spanning-tree algorithms that read the weight on every edge during their core inner loop.

Plain BFS finds the shortest path through a 1000x1000 grid by exploring outward in concentric circles, examining about a million cells. A* with a Manhattan-distance heuristic walks almost straight to the target and examines a few thousand. Both algorithms use the same priority-queue framework; the only difference is that A* adds a heuristic estimate to the cost function and biases the search toward the goal. That single addition is what powers GPS, game-pathfinding, and motion planning in robotics. **Advanced Search Algorithms** covers the search refinements that go beyond plain BFS and DFS. You will implement A* with the `f(n) = g(n) + h(n)` cost function, derive what makes a heuristic admissible, and prove the optimality guarantee under admissibility. Bidirectional search runs BFS from both source and target until the frontiers meet, cutting `O(b^d)` to `O(b^(d/2))`. Iterative Deepening DFS combines BFS-style completeness with DFS-style `O(d)` memory, using repeated depth-limited DFS. The lesson finishes with two specialized array searches: Jump search at `O(sqrt(n))` for sorted arrays where binary search is awkward, and interpolation search at `O(log log n)` expected for uniformly distributed keys. In **BFS & DFS (Intro)**, you wrote the basic skeletons. **Graph Algorithms (Core)** introduced Dijkstra's priority-queue relaxation, which A* generalizes by adding the heuristic. Next, **Game Theory** turns to two-player adversarial search.

Swap a queue for a stack inside a graph traversal and you flip from breadth-first to depth-first behavior. The visited-vertex tracking is identical, the neighbor expansion is identical, and yet one explores level by level while the other dives down the longest path first. That single data-structure swap is the entire difference between the two most-used graph algorithms in the field. **BFS & DFS (Intro)** walks through both. For BFS you will implement queue-based level-by-level exploration and use it to find shortest paths in unweighted graphs. For DFS you will see both the recursive form (which uses the call stack implicitly) and the iterative form with an explicit stack, and apply them to connectivity checks, path finding, and cycle detection. The lesson also covers the visited set that prevents infinite loops on cyclic graphs and contrasts graph traversal with tree traversal as a special case. This lesson assumes you are comfortable with three structures from the data-structures track: **Stack (LIFO)** powers iterative DFS, **Queue & Deque** powers BFS, and **Graphs: Representation Basics** gives you the adjacency list or matrix that both algorithms read from. Next, **Hashing Techniques** turns to a different building block, the hash map, which underpins many of the lookup-heavy patterns you will combine with traversal in later lessons.

Dijkstra's shortest-path algorithm silently assumes every edge weight is non-negative. Hand it a graph with one negative edge and it can produce a wrong answer with full confidence, because the greedy choice that drives the algorithm no longer reflects the true cost. Real graphs (financial arbitrage detection, currency exchange, time-aware routing) routinely contain negative edges, and that single gap motivates an entire second wave of graph algorithms. **Graph Algorithms (Advanced)** covers that wave. Minimum-spanning-tree algorithms include Kruskal's (sort edges and union components) and Prim's (grow a tree using a priority queue), along with the cut property that explains why both produce the same minimum weight. Shortest paths gain Bellman-Ford for negative edges and negative-cycle detection, plus Floyd-Warshall for all-pairs shortest paths in `O(V^3)`. Strongly connected components are tackled by Kosaraju's (two DFS passes) and Tarjan's (single DFS with low-link values). The lesson also covers articulation points, bridges, Euler paths and circuits via Hierholzer's algorithm, and a first conceptual look at NP-complete Hamiltonian paths. In **Graph Algorithms (Core)**, you implemented Dijkstra, topological sort, and cycle detection. **Union-Find (Disjoint Set Union)** gave you the near-constant-time merge-and-query primitive that makes Kruskal's MST run in `O(E log E)`. From here, **Advanced Graph Algorithms (Network Flow)** turns to capacity-constrained optimization on directed graphs.

Webpack figures out the order to compile your modules using topological sort. Google Maps figures out the route to your destination using Dijkstra. Your CI system rejects circular imports using cycle detection. The same handful of graph algorithms power an enormous slice of real infrastructure, and almost all of them are short additions to a BFS or DFS skeleton you already wrote. **Graph Algorithms (Core)** covers that handful in detail. You will implement topological sort in two ways (Kahn's BFS-with-in-degree algorithm and the DFS-reverse-postorder algorithm), cycle detection on undirected graphs (DFS with parent tracking) and on directed graphs (DFS with white/gray/black coloring), Dijkstra's shortest-path algorithm with a min-heap and the relaxation invariant that makes it work, connected-component counting via DFS or Union-Find, and bipartite checking via two-color BFS. Along the way you will see why Dijkstra fails on negative edge weights, which motivates Bellman-Ford in the advanced lesson later. In **BFS & DFS (Intro)**, you wrote the two traversal skeletons. **Weighted Graph Representation** gave you the adjacency-list-of-tuples format that Dijkstra and friends actually consume. This lesson is where those primitives turn into named algorithms with clear use cases. From here, **Greedy (Intro)** introduces a different paradigm: instead of exploring every option, commit to the locally best choice at each step.

Two seemingly different problems, the maximum amount of water you can push from a source to a sink through a network of capacitated pipes, and the minimum total capacity you must remove to disconnect the sink from the source, turn out to have the same answer for every graph. The max-flow min-cut theorem ties them together, and once you accept it a surprising number of optimization problems (image segmentation, project selection, bipartite matching) collapse into max-flow instances. **Advanced Graph Algorithms (Network Flow)** introduces the algorithms that compute that maximum flow. You will work through the Ford-Fulkerson method built on augmenting paths and the residual graph, the BFS-based Edmonds-Karp variant with its `O(V * E^2)` guarantee, and Dinic's algorithm which uses level graphs and blocking flows to reach `O(V^2 * E)`. The lesson then turns to maximum bipartite matching (Hungarian and Hopcroft-Karp), applications like airline scheduling and image segmentation, and a first look at minimum-cost flow. In **Graph Algorithms (Advanced)**, you handled MST, all-pairs shortest paths, and SCCs on edge-weighted graphs. Network flow keeps the weighted-edge model but flips the question from "shortest" to "highest throughput." Next, **String Algorithms** turns to pattern matching, the implicit automaton of a regular expression.