# 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 ```bash 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.