Files

graph-algorithms

Companion code for the ankurm.com article Graph Algorithms in Java: Dijkstra, Topological Sort and Union-Find.

Dijkstra (heap, lazy deletion, array version), Bellman-Ford as the reference answer, Kahn's topological sort (plus smallest-first, layered and recursive DFS variants), Union-Find with each optimisation switchable, and Kruskal and Prim. Every figure and console line in the article is quoted from a file in output/, which the JUnit tests write while asserting the same numbers. There is no docs/ folder: the explanations live in the article itself.

Versions

Component Version Verified against
JDK Temurin 25.0.5+8 (LTS) java -version; Adoptium available_lts_releases
JUnit 6.1.3 junit-bom maven-metadata.xml on Maven Central (latest GA)
Maven 3.9.x mvn -version

Quickstart

cd graph-algorithms
export JAVA_HOME=/path/to/jdk-25 PATH="$JAVA_HOME/bin:$PATH"
./scripts/run-all.sh      # runs 15 tests and regenerates output/*.txt

The first Maven run must be online so the plugins land in the local cache.

Source map

File What it holds
Graph.java weighted directed adjacency list
Dijkstra.java heap version with stats, O(V^2) array version, visited-set version, no-check demo
BellmanFord.java the reference answer; correct with negative edges
TopologicalSort.java kahn, kahnSmallestFirst, kahnLevels, recursive dfs, isValidOrder
UnionFind.java four strategies (naive, by size, compression, both), hop counter, maxDepth
SpanningTree.java kruskal and prim
Pitfalls.java int infinity overflow and a Union-Find whose union skips find

Captured output

File What it shows
01-dijkstra-trace.txt pop-by-pop trace on a 6-vertex graph, including two stale entries
02-dijkstra-stale-entries.txt work with and without the stale-entry check
03-dijkstra-vs-bellman-ford.txt 3000 seeded random graphs, 0 disagreements
04-negative-edges.txt one negative edge: exception, visited-set version, lazy version, Bellman-Ford
05-quadratic-vs-heap.txt work counts for the array and heap versions on a sparse and a dense graph
06-kahn-course-schedule.txt course schedule, layers, and the cyclic-graph flag
07-topological-random-agreement.txt Kahn and DFS vs a transitive-closure reference
08-recursion-depth.txt recursive DFS overflows a 512 KB stack on a 100,000-vertex chain; Kahn does not
09-union-find-chain.txt depth and hops for each Union-Find strategy
10-union-find-random-agreement.txt all four strategies vs BFS component counts
11-kruskal-prim.txt minimum spanning tree and a Kruskal/Prim cross-check
12-pitfall-int-infinity.txt Integer.MAX_VALUE + 5 makes an unreachable vertex look cheap
13-pitfall-union-without-find.txt parent[a] = b loses a connection

Operation counts are deterministic (seeded inputs); nothing in output/ is a timing.