You have cities and roads, tasks and prerequisites, friends and friendships, and a question about them: what is the cheapest route, in what order can these jobs run, are these two things connected? Each of those is a graph problem, and a surprisingly small set of algorithms answers most of them. This article builds the three that interviews and real systems keep asking for — Dijkstra for cheapest paths, Kahn’s algorithm for ordering tasks with prerequisites, and Union-Find for “are these connected?” — in plain Java, and then breaks each one on purpose so you recognise the symptom when you meet it.
Everything below was compiled and run. Every number and console line is quoted from a file in the companion module, which a JUnit test writes while asserting the same figures, so if a number in this article stops being true the build fails. You do not need to know graphs beforehand; you need to be comfortable with arrays, lists and PriorityQueue. If you want the traversal basics first, the older posts on BFS and DFS cover them.
Versions this was tested against. JDK Temurin 25.0.5+8 (the current LTS per Adoptium’savailable_lts_releases), JUnit 6.1.3 (latest GA injunit-bom’smaven-metadata.xml), Maven 3.9. No framework: the module is plain Java. Source: java-interview-lab/graph-algorithms (one commit, 15 tests, 13 captured transcripts). There is nodocs/folder; the deeper material sits in the collapsible sections of this page.
A graph is just “who can I reach from here”
A graph has vertices (the things: cities, tasks, people) and edges (the links between them). An edge can carry a weight, such as a distance or a cost, and can be directed (one-way, like a prerequisite) or undirected (two-way, like a road). The only decision that matters before you write any algorithm is how to store it. The usual answer is an adjacency list: for every vertex, a list of the edges that leave it.
The picture and the lists are the same graph. This six-vertex graph is the running example for the whole article, so it is worth a moment: from A you can go to B at cost 7, to C at cost 9, or straight to F at cost 14. Notice that the direct road to F (14) is not the cheapest way there — going through C costs 9 + 2 = 11. Finding that automatically is what Dijkstra does.
The code, from Graph.java:
public Graph addEdge(int from, int to, int weight) {
Edge e = new Edge(from, to, weight);
adjacency.get(from).add(e);
edges.add(e);
if (weight < 0) {
hasNegativeEdge = true;
}
return this;
}
An undirected edge is simply two directed edges, one each way (addUndirected calls addEdge twice). The graph also remembers whether it has seen a negative weight; that flag becomes important in the Dijkstra section.
Going deeper: lists versus matrices, and what the other posts cover
An adjacency matrix uses a V×V grid and answers “is there an edge from u to v?” in constant time, at the cost of V² memory even when almost nothing is connected. An adjacency list uses memory proportional to V + E and lets you walk a vertex’s neighbours without skipping empty cells. Real graphs (road maps, dependency graphs, social networks) are sparse, which is why every algorithm in this article assumes a list.
- Graph traversal without weights: Implementing BFS in Java and Implementing DFS in Java.
- Source for this section: Graph.java.
Cheapest route: Dijkstra settles the closest unsettled vertex, over and over
Suppose you stand at A and want the cheapest cost to every other vertex. Dijkstra’s idea fits in one sentence: keep a best-known cost for every vertex, repeatedly take the not-yet-finished vertex with the smallest best-known cost, declare it finished, and see whether going through it makes any neighbour cheaper. Because every weight is non-negative, the vertex with the smallest cost can never be improved later — any other route to it would have to pass through something at least as expensive. That is why “finished” is safe.
To always find the smallest best-known cost quickly, the implementation keeps candidates in a PriorityQueue (a binary heap). Here is the full method, including the optional trace hook the next output uses. The lines to read are the while loop and the if (candidate < dist[...]) test, which is the relaxation: “is the route through u better than what I knew?”
The code, from Dijkstra.java:
private static Result run(Graph g, int source, boolean skipStale, boolean checkNegative, Consumer<String> trace) {
if (checkNegative && g.hasNegativeEdge()) {
throw new IllegalArgumentException("Dijkstra needs non-negative weights; use Bellman-Ford instead");
}
int n = g.size();
long[] dist = new long[n];
int[] parent = new int[n];
Arrays.fill(dist, INF);
Arrays.fill(parent, -1);
dist[source] = 0;
PriorityQueue<Entry> pq = new PriorityQueue<>(Comparator.comparingLong(Entry::dist));
pq.add(new Entry(source, 0));
int pushes = 1;
int pops = 0;
int stale = 0;
int scans = 0;
int relaxations = 0;
while (!pq.isEmpty()) {
Entry e = pq.poll();
pops++;
int u = e.node();
if (e.dist() > dist[u]) {
stale++;
if (trace != null) {
trace.accept("pop " + u + " @" + e.dist() + " stale (best known is " + dist[u] + ")"
+ (skipStale ? " -> skipped" : " -> expanded anyway"));
}
if (skipStale) {
continue;
}
} else if (trace != null) {
trace.accept("pop " + u + " @" + e.dist() + " settled");
}
for (Edge edge : g.from(u)) {
scans++;
long candidate = dist[u] + edge.weight();
if (candidate < dist[edge.to()]) {
dist[edge.to()] = candidate;
parent[edge.to()] = u;
pq.add(new Entry(edge.to(), candidate));
pushes++;
relaxations++;
if (trace != null) {
trace.accept(" relax " + u + " -> " + edge.to() + " dist[" + edge.to() + "] = " + candidate);
}
}
}
}
return new Result(dist, parent, new Stats(pushes, pops, stale, scans, relaxations));
}
Running it on the example graph from A gives this trace. Each pop is one vertex leaving the heap; each indented relax is a neighbour whose cost just dropped.
Real output, from 01-dijkstra-trace.txt:
pop 0 @0 settled
relax 0 -> 1 dist[1] = 7
relax 0 -> 2 dist[2] = 9
relax 0 -> 5 dist[5] = 14
pop 1 @7 settled
relax 1 -> 3 dist[3] = 22
pop 2 @9 settled
relax 2 -> 3 dist[3] = 20
relax 2 -> 5 dist[5] = 11
pop 5 @11 settled
relax 5 -> 4 dist[4] = 20
pop 5 @14 stale (best known is 11) -> skipped
pop 4 @20 settled
pop 3 @20 settled
pop 3 @22 stale (best known is 20) -> skipped
Real output, from 01-dijkstra-trace.txt:
dist[A] = 0
dist[B] = 7
dist[C] = 9
dist[D] = 20
dist[E] = 20
dist[F] = 11
cheapest path to E: A -> C -> F -> E (cost 20)
Follow vertex F. When A is popped, F is queued at 14 (the direct road). When C is popped at 9, the route through C offers 9 + 2 = 11, so F is updated and queued again at 11. F therefore sits in the heap twice, and that is not a bug. The next section explains why, because it is the single detail that beginners find most confusing and experts most often get subtly wrong.
Going deeper: the path itself, and the cost of the algorithm
Distances alone do not tell you the route. The parent array records, for each vertex, which vertex last improved it; walking it backwards from the target and reversing gives the path, which is how the trace above produced A -> C -> F -> E. Asking for the path to an unreachable vertex returns an empty list rather than a bogus route.
With a binary heap each push or pop is O(log n), and each edge causes at most one push, so the whole run is O((V + E) log V) in the usual textbook accounting. The Java Javadoc for PriorityQueue states that offer and poll are logarithmic and that remove(Object) and contains are linear, which matters in the next section. Further reading: PriorityQueue Javadoc (Java 25); an older C version of the same idea is on this site as Implementation of Dijkstra Algorithm in C.
Why the same vertex can be in the heap twice (and why that is fine)
When F’s cost drops from 14 to 11, the textbook says “decrease the key” of F inside the heap. Java’s PriorityQueue has no such operation. The only way to change an element is remove(Object), which is linear time and would make the whole algorithm slower. So the code takes the cheaper route: it leaves the old, worse entry where it is, pushes a new entry with the better cost, and later ignores the old one when it surfaces. This is called lazy deletion.
This is the same trace as before, drawn as the sequence of heap pops. The two dashed boxes are the stale entries: F at 14 and D at 22 were correct when queued and out of date by the time they came out. The check that recognises them is one line in the method above: if (e.dist() > dist[u]) — the entry’s cost is worse than the best known cost, so skip it. How much does that line matter on a bigger graph? The module runs the algorithm on a seeded random graph with and without it:
Real output, from 02-dijkstra-stale-entries.txt:
with check : Stats[pushes=2831, pops=2831, stalePops=849, edgeScans=9915, relaxations=2830]
without check : Stats[pushes=2831, pops=2831, stalePops=849, edgeScans=14168, relaxations=2830]
same distances: true
Two facts are worth reading off. First, the distances are identical, so skipping stale entries is an optimisation, not a correctness requirement — the relaxation test already refuses to make anything worse. Second, 849 of the 2,831 pops (about 30%) were stale, and without the skip the loop scanned 14,168 edges instead of 9,915, roughly 43% more work spent re-expanding vertices that were already finished.
A common bug, and what it looks like. Writing if (visited[u]) continue; with a boolean array instead of the distance comparison is fine for non-negative weights, but it quietly bakes in the assumption that a vertex is final the first time it is popped. The next section shows what that costs the moment a weight is negative.
Going deeper: indexed heaps, and how the cost really behaves
Pushing a duplicate means the heap can hold up to E entries rather than V, so the cost is O(E log E), which is the same as O(E log V) because E is at most V². An indexed priority queue supports a genuine decrease-key and keeps the heap at V entries; it is more code and only pays off on very large dense graphs. The standard library does not offer one.
- Run the experiment yourself:
staleEntriesCostWorkButNotCorrectnessin DijkstraTest.java.
What breaks Dijkstra: one negative edge
The safety argument above leaned on “every weight is non-negative”. Remove that and the argument fails: a vertex that looked finished can later be reached more cheaply through a negative edge. The test uses the smallest graph that shows it: A→B costs 1, A→C costs 2, and C→B costs −5, so the true cheapest cost to B is 2 + (−5) = −3.
Real output, from 04-negative-edges.txt:
Dijkstra.run(g, A) throws : Dijkstra needs non-negative weights; use Bellman-Ford instead
visited-set version, dist[B] : 1
lazy version, check removed, dist[B]: -3 (pops 4)
Bellman-Ford, dist[B] : -3
Four answers to one question. The checked Dijkstra.run refuses the graph with an exception, which is the behaviour you want from a library. The “visited set” version, the one many tutorials write, returns 1, silently wrong. Bellman-Ford, which tolerates negative edges, returns −3. And the lazy-deletion version with the safety check removed also returns −3 here: B is popped at 1, then pushed again at −3 when C is expanded, and the stale-entry test lets that cheaper entry through, so B is expanded twice (4 pops in total). Do not read that as “lazy deletion handles negative edges”: re-expansion can repeat many times on larger graphs, and a negative cycle would loop forever. Use Bellman-Ford when negative weights are possible.
To trust the fast version at all, the tests compare it against Bellman-Ford on random graphs:
Real output, from 03-dijkstra-vs-bellman-ford.txt:
cases checked : 3000
cases with an unreachable vertex: 2323
disagreements : 0
3,000 seeded graphs, 2,323 of which had at least one unreachable vertex (so that case is exercised heavily), and the two algorithms never disagreed.
Going deeper: the int-infinity trap in Bellman-Ford
Bellman-Ford looks at every edge on every pass, including edges that leave vertices you have not reached yet. If “infinity” is Integer.MAX_VALUE, adding any weight to it overflows into a large negative number, which then looks like a fantastic bargain:
Real output, from 12-pitfall-int-infinity.txt:
Integer.MAX_VALUE + 5 = -2147483644
int version, dist[3] : -2147483644
long + check, dist[3] : unreachable (INF)The fix used in BellmanFord.java is a long sentinel plus an explicit “is it reachable?” check before adding. Dijkstra avoids the problem by construction, because it only ever pops vertices it has already reached. The wrong version lives in Pitfalls.java.
Heap or plain array? Count the work instead of guessing
There is a simpler Dijkstra with no heap: to find the closest unfinished vertex, scan all V vertices. That costs V² steps no matter how few edges exist. The heap version costs more per step but does far less total work on sparse graphs. Rather than time them (timings drift between machines), the module counts the work each one does on a sparse and a dense graph:
Real output, from 05-quadratic-vs-heap.txt:
sparse V=2000 E=8000:
array version : min-scan steps 3916000
heap version : pushes 2541, pops 2541, edge scans 7784
dense V=600 E=150000:
array version : min-scan steps 360000
heap version : pushes 2292, pops 2292, edge scans 150000
On the sparse graph the array version does 3,916,000 minimum-search steps (fewer than 2,000² = 4,000,000 only because the loop stops when no reachable vertex is left) while the heap version does about 2,500 pops and 7,784 edge scans — a gap of several hundred times. On the dense graph, 600 vertices and 150,000 edges, the picture changes: the array version does 360,000 steps and the heap version 2,292 pops, but both must scan all 150,000 edges, so the heap’s advantage shrinks to a modest saving. The honest takeaway is the usual one: the heap wins clearly on sparse graphs, which is nearly every graph you will meet, and the array version is a reasonable choice only for small, dense inputs.
Going deeper: reading the counters
The heap version’s pushes and pops are equal because every pushed entry is eventually popped (stale ones included). The dense graph’s 2,292 pushes for 600 vertices means a vertex was improved about four times on average before it was final, which is the stale-entry effect from the previous section at work. The tests assert that both versions return identical distances before printing a single count (quadraticVersusHeap in DijkstraTest.java).
Ordering tasks with prerequisites: topological sort and Kahn’s algorithm
A different question: given courses where some must be taken before others, in what order can you take them all? Here the edges are directed — “A before B” — and the answer is a topological order: a list where every arrow points forward. One exists exactly when the graph has no cycle (you cannot take two courses that each require the other).
Kahn’s algorithm is the most direct way to compute it. Count how many unmet prerequisites each vertex has (its indegree). Anything at zero can be taken now. Take one, then reduce the count of everything it unlocks; whatever reaches zero becomes available.
The module models seven courses with eight prerequisite links. Read the columns left to right: Intro and Maths have no prerequisites, so they are the first column; once they are done, DSA and DBMS become available; and so on. The longest chain of dependencies (Intro, DSA, OS, Networks) has four courses, which is why four semesters is the minimum. Here is the code:
The code, from TopologicalSort.java:
public static Order kahn(int n, int[][] edges) {
List<List<Integer>> adj = adjacency(n, edges);
int[] indegree = indegrees(n, edges);
Deque<Integer> ready = new ArrayDeque<>();
for (int v = 0; v < n; v++) {
if (indegree[v] == 0) {
ready.add(v);
}
}
List<Integer> order = new ArrayList<>();
while (!ready.isEmpty()) {
int u = ready.poll();
order.add(u);
for (int v : adj.get(u)) {
if (--indegree[v] == 0) {
ready.add(v);
}
}
}
return new Order(order, order.size() == n);
}
Real output, from 06-kahn-course-schedule.txt:
kahn (queue order) : Intro, Maths, DBMS, DSA, OS, Networks, Compilers acyclic=true
kahn (smallest first): Intro, Maths, DSA, DBMS, OS, Networks, Compilers acyclic=true
semester 1 : Intro, Maths
semester 2 : DSA, DBMS
semester 3 : OS
semester 4 : Networks, Compilers
Two orders are printed because “the” topological order is not unique. The plain version follows queue order; the second uses a heap to always pick the smallest course number, which makes the output reproducible. The semester lines come from a layered variant (kahnLevels) that processes a whole column at once — everything in a column can run in parallel, which is exactly how build tools and job schedulers use this.
Now the case that matters: a cycle. The test adds the links 1→2, 2→1 and 2→3 on top of an independent vertex 0.
Real output, from 06-kahn-course-schedule.txt:
cycle 1->2->1 plus 2->3, kahn returns: [0] acyclic=false
(vertex 0 is the only one that could be ordered; the flag is the only signal of the cycle)
Always check acyclic. On a cyclic graph Kahn does not throw; it simply stops early and returns the part it could order, here just vertex 0. Code that uses the order without checking the flag will silently skip every vertex that is in, or behind, the cycle. The test that checks this against a brute-force transitive-closure reference is below.
Real output, from 07-topological-random-agreement.txt:
cases checked : 3000
cases with a cycle : 2016
cases acyclic (orders valid): 984
disagreements : 0
3,000 seeded random graphs, 2,016 containing a cycle and 984 acyclic. For the acyclic ones the test also verifies each returned order edge by edge with isValidOrder, so “it looks sorted” is never the standard.
Going deeper: the DFS alternative and why it can crash
The other classic method runs a depth-first search and reads the vertices off in reverse finishing order. It is shorter to write and detects a cycle when a search reaches a vertex that is still on its own path. Its weakness is the call stack: recursion depth equals the longest path in the graph. The module runs it on a plain 100,000-vertex chain, on a thread given a 512 KB stack so the result does not depend on machine defaults:
Real output, from 08-recursion-depth.txt:
recursive DFS : StackOverflowError
Kahn : ordered 100000 vertices, acyclic=trueKahn uses an explicit queue on the heap, not the call stack, so graph depth cannot overflow it. If you prefer the DFS approach for large inputs, write it iteratively. Both implementations are in TopologicalSort.java, along with isValidOrder, the checker the tests use.
Are these two connected? Union-Find keeps a forest of sets
The third question: given a stream of “A is linked to B” facts, are two particular things in the same group, and how many groups are there? You could run BFS after every new fact, but that repeats work. Union-Find (also called a disjoint-set union) answers in nearly constant time by storing each group as a tree where every element points to a parent, and the root of the tree is the group’s name.
It has two operations. find(x) follows parent pointers from x up to the root. union(a, b) finds both roots and, if they differ, hangs one root under the other. If the roots are the same, the two were already connected — which is also how you detect a cycle in an undirected graph.
The code, from UnionFind.java:
/** The representative of x's set. Counts every parent pointer followed in {@link #hops()}. */
public int find(int x) {
int root = x;
while (parent[root] != root) {
root = parent[root];
hops++;
}
if (strategy.compression) {
while (parent[x] != root) {
int next = parent[x];
parent[x] = root;
x = next;
}
}
return root;
}
/** Joins the sets of a and b. Returns false when they were already in the same set. */
public boolean union(int a, int b) {
int ra = find(a);
int rb = find(b);
if (ra == rb) {
return false;
}
if (strategy.bySize && size[ra] > size[rb]) {
int tmp = ra;
ra = rb;
rb = tmp;
}
parent[ra] = rb;
size[rb] += size[ra];
components--;
return true;
}
Notice that the class takes a Strategy and counts every parent pointer it follows (hops). That is deliberate: it lets us measure what the two famous optimisations buy instead of just asserting it. Union by size hangs the smaller tree under the larger. Path compression makes every vertex visited during a find point straight at the root afterwards. The test joins 0–1, then 1–2, then 2–3, all the way up to 20,000 vertices — the worst order for the naive version — then calls find(0) twice:
Without any optimisation the structure is a chain, so finding vertex 0 means walking the whole chain. With union by size it is a flat star. The numbers confirm the drawing:
Real output, from 09-union-find-chain.txt:
NAIVE max depth 19999 | find(0) #1: 19999 hops | find(0) #2: 19999 hops
BY_SIZE max depth 1 | find(0) #1: 1 hops | find(0) #2: 1 hops
COMPRESSION max depth 19999 | find(0) #1: 19999 hops | find(0) #2: 1 hops
BY_SIZE_AND_COMPRESSION max depth 1 | find(0) #1: 1 hops | find(0) #2: 1 hops
Three things stand out. The naive version pays 19,999 hops on every call, forever. Compression alone fixes the second call (19,999 hops, then 1) but still pays the full price once. Union by size avoids the long chain in the first place on this input. Is union by size therefore enough on its own? Not on every input: when sets of equal size keep merging, depth grows by one per round. The test builds that pattern for 16,384 vertices (214), and the real output says what happens:
Real output, from 09-union-find-chain.txt:
Tournament pattern, n=16384: round r joins sets of size 2^r, so equal sizes meet every time
NAIVE max depth 14
BY_SIZE max depth 14
COMPRESSION max depth 13
BY_SIZE_AND_COMPRESSION max depth 13
Union by size reaches depth 14, which is exactly log2(16,384): that logarithm is the bound union by size guarantees, and this input meets it. Both optimisations together stay at 13 here because the find calls inside union compress paths as they go. Together they give the near-constant amortised time that makes Union-Find practical (the textbook name for the bound is the inverse Ackermann function; for any input you can store it is at most 4 or 5).
The classic Union-Find bug. Writingparent[a] = bwithout callingfindfirst, because “a and b are the elements”. They are not necessarily roots. Afterunion(0,1)thenunion(0,2)the buggy version overwrites vertex 0’s parent and forgets that 0 and 1 were joined.
Real output, from 13-pitfall-union-without-find.txt:
buggy connected(0,1): false
correct connected(0,1): true
The code, from Pitfalls.java:
public void union(int a, int b) {
parent[a] = b; // BUG: a and b are not necessarily roots
}
Going deeper: checking all four strategies against BFS
The strategies differ in speed, not in answers, and the tests hold them to that. For 2,000 seeded random edge lists every strategy must report the same number of components as a plain BFS:
Real output, from 10-union-find-random-agreement.txt:
cases checked : 2000
strategies : [NAIVE, BY_SIZE, COMPRESSION, BY_SIZE_AND_COMPRESSION]
disagreements : 0Union-Find shines when edges arrive over time (network connectivity, merging accounts, percolation). If you only need the components of a fixed graph once, a single BFS or DFS is just as good. Related posts on this site: Dynamic Programming in Java and Sliding Window and Two Pointers are the same interview series.
Kruskal and Prim: where Union-Find earns its keep
A minimum spanning tree connects every vertex of an undirected graph using the cheapest total set of edges and no cycles — think of laying cable between towns for the least cost. Kruskal’s method is greedy and short: sort the edges by weight, then take each edge unless its two ends are already connected. “Already connected?” is exactly the question Union-Find answers.
The code, from SpanningTree.java:
public static Result kruskal(Graph g) {
List<Edge> sorted = new ArrayList<>();
for (Edge e : g.edges()) {
if (e.from() < e.to()) { // each undirected edge is stored twice; keep one direction
sorted.add(e);
}
}
sorted.sort(Comparator.comparingInt(Edge::weight));
UnionFind uf = new UnionFind(g.size(), UnionFind.Strategy.BY_SIZE_AND_COMPRESSION);
List<Edge> chosen = new ArrayList<>();
long total = 0;
for (Edge e : sorted) {
if (uf.union(e.from(), e.to())) {
chosen.add(e);
total += e.weight();
}
}
return new Result(total, chosen, uf.components() == 1);
}
Real output, from 11-kruskal-prim.txt:
Kruskal total weight: 33
C - F (2)
D - E (6)
A - B (7)
A - C (9)
E - F (9)
Prim total weight : 33
On the example graph the cheapest tree costs 33 using five edges. Prim’s method, which grows one tree from vertex 0 using a heap, must reach the same total, and the test checks that on 2,000 random graphs too:
Real output, from 11-kruskal-prim.txt:
random graphs checked : 2000
of which disconnected : 1330
Kruskal/Prim disagreements : 0
1,330 of those graphs were disconnected. For those there is no spanning tree, so both functions return a spanning forest and set spanning to false — another flag to check rather than assume.
Going deeper: which one to pick
Both run in O(E log E) with these data structures, so pick whichever matches how your graph is already stored: Kruskal works on an edge list and needs a sort plus a Union-Find, Prim works on adjacency lists and needs a heap. The test kruskalAndPrimAgree in SpanningTreeTest.java shows how to cross-check one against the other.
Which algorithm do I need?
| Your question | Use | Check before trusting it |
|---|---|---|
| Cheapest route, weights never negative | Dijkstra | Negative edge? Use Bellman-Ford instead |
| Cheapest route, weights may be negative | Bellman-Ford | Check negativeCycle |
| Order tasks with prerequisites | Kahn’s algorithm | Check acyclic on the result |
| Are two things in the same group, as links arrive? | Union-Find | Call find on both sides inside union |
| Cheapest way to connect everything | Kruskal or Prim | Check spanning for disconnected input |
Should you write these yourself? For interviews and for understanding, yes: each one is under fifty lines and the failure modes above are exactly what interviewers probe. For production work on a real graph, prefer a maintained graph library over a hand-rolled version, and keep these tests-against-a-reference habits when you wire it in. Also keep the scale in mind: a graph with a few thousand vertices does not need clever data structures, and a graph that does not fit in memory needs a different tool altogether.
Run it yourself
Clone the repository, switch to JDK 25, and run one script; it executes all 15 tests and rewrites every output/*.txt file quoted above.
$ git clone https://ankurm.com/git.app/asmhatre/java-interview-lab.git
$ cd java-interview-lab/graph-algorithms
$ ./scripts/run-all.sh
That script is scripts/run-all.sh; the quickstart and a table of every transcript are in the module’s README.md. The first Maven run must be online so plugins land in the local cache. Operation counts are deterministic because the inputs are seeded; nothing in the transcripts is a timing.
Further reading
- Companion module: java-interview-lab/graph-algorithms (source, tests and all 13 transcripts).
- On this site: Implementing BFS in Java, Implementing DFS in Java, Dijkstra in C, Binary Tree Traversals in Java, Stack and Queue Problems in Java.
- PriorityQueue Javadoc, Java 25 — the complexity notes for
offer,pollandremove(Object).
No Comments yet!