Graph Theory Algorithms

Learn beginner-friendly tree algorithms by implementing recursive leaf-sum and binary-tree height calculations using depth-first search, with clear pseudocode and base-case strategies.

Root a tree with depth-first search to obtain a rooted tree with directed edges. The method uses a designated root, maintains parent pointers, and avoids revisiting the parent during traversal.

Find the center of a tree by the middle of the longest path or by peeling leaf layers, using node degrees to prune until 1 or 2 centers remain.

Learn how topological sort produces a valid ordering for directed acyclic graphs, useful for course prerequisites and program build dependencies, by performing depth-first search and producing a reverse ordering.

Explore the eager implementation of Dijkstra's shortest path algorithm in Java, including an indexed min d-ary heap, graph representation, edge relaxation, and path reconstruction.

Learn the Floyd-Warshall all-pairs shortest path solver using an adjacency matrix, distance and next matrices, handling infinity and negative cycles, and reconstructing paths between node pairs.

Learn how to detect bridges (cut edges) and articulation points (cut vertices) in undirected graphs using a depth-first search with low-link values, and implement a linear-time algorithm.

Explore the algorithm to find bridges and articulation points in an undirected adjacency-list graph, with Java source code; learn how depth-first search and low-link values identify these points.

Discover Tarjan's algorithm for finding strongly connected components by maintaining a stack and updating low-link values during DFS to identify SCCs in linear time.

Explore the existence of eulerian paths and circuits in directed and undirected graphs by analyzing node degrees, in-degrees, out-degrees, and connectivity.

Explore the Eulerian path algorithm's source code by instantiating the solver with a directed graph and retrieving the path, with in and out degree tracking, DFS, and GitHub-hosted examples.

Discover how to compute maximum flow with the Ford-Fulkerson method on a flow graph using augmenting paths and residual edges to update bottlenecks.

Explore the Ford-Fulkerson max flow algorithm implemented with depth-first search in Java, including edge and residual edge handling, augmenting paths, and a concrete max flow example for graph theory algorithms.

Explore unweighted bipartite matching by framing it as a max flow problem, building a source–bipartite graph–sink network, and extracting a maximum cardinality matching from the resulting flow.

Turns number pairs into a bipartite flow problem and solves it with max flow, building a graph from inputs to unique answers and deducing the operator for each pair.

Edmonds-Karp uses a breadth-first search to find the shortest augmenting path in the Ford-Fulkerson framework, delivering max flow with a strongly polynomial time bound O(V E^2).

Explore the Edmonds-karp network flow algorithm with Java source code, implement BFS-based augmenting paths, compute bottlenecks, and update maximum flow in a reusable solver.

Explore capacity scaling, a heuristic for network flow that prioritizes large edges to reach max flow quickly, using a decreasing delta threshold to guide augmenting paths.

Explore the capacity scaling network flow solver in Java, focusing on Delta, augmenting paths, and depth-first search to compute the maximum flow.

Dinic's algorithm finds maximum flow by building a level graph with BFS and saturating paths via DFS to a blocking flow, pruning dead ends, enabling maximum matching for bipartite graphs.

Learn the Dinic's algorithm implementation in Java, building level graphs with breadth-first search, finding blocking flows via depth-first search, and using the next array to prune edges toward maximum flow.

Learn how Prim's algorithm constructs a minimum spanning tree on a weighted graph using the lazy version, via a priority queue, visited nodes, and handling stale edges.

Learn Prim's eager algorithm for minimum spanning trees, using an index priority queue to maintain vertex edge pairs and relax edges. Compare with the lazy version and discuss graph performance.

Discover prim's minimum spanning tree source code in Java, focusing on the eager implementation, edge relaxation, and the indexed priority queue that computes the MST cost and edges.

Explore a Java min sparse table implementation that supports fast min range queries, using a dynamic programming sparse table and an index table to track positions.

Learn to find the lowest common ancestor in rooted trees using an Euler tour, depth tracking, and a sparse table for fast queries.