Graph Algorithms
Traversals, shortest paths, spanning trees, connectivity and matchings on graphs.
48 articles~332 min total
0/48
Graph traversal
- Graphs: Terminology and RepresentationVertices, edges and the vocabulary of graph problems, and the three ways to store a graph in Python (adjacency list, matrix, edge list).5 minBeginner
- Breadth-First SearchVisit vertices in order of distance from a source with a queue: shortest paths in unweighted graphs, grids and more.6 minBeginner
- Depth-First SearchExplore a graph as deep as possible before backtracking; entry and exit times, edge classification, and how to avoid Python's recursion limit.7 minBeginner
Connectivity
- Connected ComponentsSplit an undirected graph into its connected pieces with a traversal (or a DSU) and count or label them.4 minBeginner
- Finding BridgesFind the edges whose removal disconnects the graph in O(n + m) using DFS entry times and low-link values.5 minAdvanced
- Finding Articulation PointsFind the vertices whose removal disconnects the graph, in O(n + m), using the same low-link values as for bridges.4 minAdvanced
- Strongly Connected ComponentsPartition a directed graph into mutually reachable groups with Kosaraju's or Tarjan's algorithm, and build the condensation DAG.8 minAdvanced
- Finding Bridges OnlineMaintain the number of bridges while edges are added one by one, using a forest of 2-edge-connected components, two DSUs and re-rooting of the smaller tree.8 minAdvanced
- Strong OrientationDirect the edges of an undirected graph to make it strongly connected (Robbins' theorem) with one DFS, or to minimize the number of strongly connected components.6 minAdvanced
- Edge and Vertex ConnectivityHow many edges or vertices must be removed to disconnect a graph? Whitney's inequalities and the max-flow computation of both connectivities.8 minAdvanced
Shortest paths
- Dijkstra's AlgorithmShortest paths from one source in a graph with non-negative weights, in O((n + m) log n) with a heap, plus path restoration.7 minIntermediate
- Bellman-Ford AlgorithmShortest paths with negative edge weights, detecting and extracting negative cycles, and the queue-based SPFA optimization.7 minIntermediate
- 0-1 BFSShortest paths in a graph whose edges weigh 0 or 1 in O(n + m) with a deque, and Dial's algorithm for small integer weights.5 minIntermediate
- Floyd-Warshall AlgorithmAll-pairs shortest paths in O(n³) with three nested loops, path reconstruction, negative cycles, and a much faster Python formulation.7 minIntermediate
- Dijkstra on Sparse Graphs: Priority Queue VariantsWhy the O(n²) Dijkstra is wasteful on sparse graphs, and how heap variants (lazy deletion, decrease-key, packed integers) compare in Python.9 minIntermediate
- D'Esopo-Pape AlgorithmA deque-based single-source shortest path algorithm that is often faster than Dijkstra and Bellman-Ford and works with negative edges, but has an exponential worst case.5 minIntermediate
- Paths of Fixed Length: Matrix ExponentiationCount the walks of exactly k edges with the k-th power of the adjacency matrix, and find the shortest walks with exactly k edges with a (min, +) matrix power.8 minAdvanced
- Finding a Negative CycleDetect and extract a negative-weight cycle with Bellman-Ford started from all vertices at once, and find every pair of vertices with arbitrarily short paths with Floyd-Warshall.6 minIntermediate
Spanning trees
- Minimum Spanning Tree: Kruskal's AlgorithmConnect all vertices at the smallest total cost by sorting edges and joining components with a disjoint set union, in O(m log m).6 minIntermediate
- Minimum Spanning Tree: Prim's AlgorithmGrow the spanning tree from one vertex by always adding the cheapest edge leaving it, in O(m log n) with a heap or O(n²) for dense graphs.6 minIntermediate
- Kruskal's Algorithm: The Simplest Implementation and Its ProofProperties of minimum spanning trees, Kruskal's algorithm with a plain tree-id array in O(M log N + N²), and the exchange-argument proof of correctness.7 minIntermediate
- Second Best Minimum Spanning TreeThe second best spanning tree differs from the MST by one edge swap; find the cheapest swap by trying every non-tree edge and taking the maximum edge on its tree path with binary lifting.9 minAdvanced
- Kirchhoff's Theorem: Counting Spanning TreesThe number of spanning trees of a graph equals any cofactor of its Laplacian matrix, computed with a determinant; connections to Cayley's formula and electrical resistance.6 minAdvanced
- Prüfer Code and Cayley's FormulaEncode a labeled tree as a sequence of n−2 numbers, decode it back in linear time, and derive Cayley's formula and the number of ways to connect a graph.10 minAdvanced
Trees and LCA
- Lowest Common Ancestor: Binary LiftingAnswer "lowest common ancestor of u and v" and k-th-ancestor queries on a rooted tree in O(log n) after O(n log n) preprocessing.6 minAdvanced
- Lowest Common Ancestor: Euler Tour and Range MinimumReduce LCA to a range-minimum query over the Euler tour of the tree, and answer it with a sparse table (O(1)), a segment tree (O(log n)), or sqrt-decomposition.8 minAdvanced
- LCA in O(1) with Linear Preprocessing: Farach-Colton and BenderSplit the Euler-tour height array into small blocks: a sparse table over block minima, and precomputed answers for all ±1 block shapes, gives LCA queries in O(1) after O(n) preprocessing.8 minAdvanced
- Range Minimum Query via LCA and the Cartesian TreeTurn a static range-minimum query on an array into an LCA query on its Cartesian tree, which the Farach-Colton–Bender algorithm answers in O(1) after linear preprocessing.7 minAdvanced
- LCA: Tarjan's Offline AlgorithmAnswer all LCA queries in one DFS with a disjoint set union, in O(n + m) total time, when the queries are known in advance.6 minAdvanced
- Painting Edges of a Tree (Euler Tour + Fenwick Tree)Paint or unpaint edges and count the painted edges on any tree path in O(log n): list every edge twice in the Euler tour and take a difference of two prefix sums.7 minAdvanced
- Heavy-Light DecompositionSplit a tree into heavy paths so that any root path crosses O(log n) of them, and answer path queries and updates with one segment tree over the flattened positions.10 minAdvanced
- Centroid DecompositionRecursively split a tree at its centroid to get a centroid tree of depth O(log n); count paths of a given length and answer nearest-marked-vertex queries.11 minAdvanced
Flows and matchings
- Checking Whether a Graph Is BipartiteTwo-colour a graph with BFS so that every edge joins different colours, or find an odd cycle that proves it impossible.4 minBeginner
- Kuhn's Algorithm: Maximum Bipartite MatchingPair up as many left and right vertices as possible using augmenting paths, in O(V·E).5 minAdvanced
- Maximum Flow: Edmonds-Karp and DinicPush as much "stuff" as possible through a capacitated network with augmenting paths, and see why max flow equals min cut.9 minAdvanced
- Maximum Flow: Dinic's AlgorithmDinic's algorithm finds a maximum flow in O(V²E) by repeatedly building a layered network and saturating it with a blocking flow; on unit networks it runs in O(E√V).9 minAdvanced
- Maximum Flow: the MPM AlgorithmThe Malhotra–Kumar–Maheshwari algorithm finds a blocking flow by repeatedly pushing the smallest vertex potential through the layered network, for O(V³) total time.8 minAdvanced
- Maximum Flow: the Push-Relabel AlgorithmInstead of augmenting paths, push excess flow downhill along a height function, relabeling stuck vertices, until the preflow becomes a maximum flow in O(V²E).7 minAdvanced
- Push-Relabel with Highest-Label SelectionAlways discharging a vertex of maximum height improves the push-relabel algorithm to O(V·E + V²√E), at most O(V³).5 minAdvanced
- Flows with Demands (Lower Bounds)Find a flow in which every edge must carry at least its demand: reduce to an ordinary maximum flow with a super source and sink, and find the minimum such flow by binary search.8 minAdvanced
- Minimum-Cost Flow: Successive Shortest PathsSend K units of flow from s to t at minimum cost by repeatedly augmenting along a cheapest residual path, using SPFA or Dijkstra with potentials.10 minAdvanced
- The Assignment Problem via Min-Cost FlowModel the assignment problem as a minimum-cost flow on a bipartite network and solve it with successive shortest paths in O(N³) (with Dijkstra) or O(N⁴) (with Bellman-Ford).5 minAdvanced
- Global Minimum Cut: Stoer-WagnerFind the minimum-weight cut of an undirected graph without any flow: run maximum-adjacency orderings and merge the last two vertices of each phase, in O(n³).6 minAdvanced
- The Hungarian Algorithm for the Assignment ProblemSolve the assignment problem in O(n²m) with potentials on rows and columns, maintained by growing an alternating tree; a 20-line implementation.6 minAdvanced
Ordering
- Topological SortingOrder the vertices of a DAG so that every edge goes forward, with Kahn's algorithm or DFS, and use it for dependency and DP problems.7 minIntermediate
- Finding a Cycle in a GraphDetect a cycle and recover its vertices in O(n + m), in directed graphs with DFS colours and in undirected graphs by tracking the parent edge.6 minIntermediate
- Eulerian Path and CircuitWalk every edge exactly once — when it is possible and how to construct the walk with Hierholzer's algorithm in O(m).7 minAdvanced