Graph-related greedy

Kruskal's algorithm sorts all edges by weight and goes through them in order, adding an edge unless it would close a cycle. A **union-find** structure answers 'are these two vertices already connected?' in near-constant time. In the “Classic” preset the algorithm accepts 4 edges for a total weight of 11, and the “Cycle edge rejected” preset accepts 0-1, 1-2 and 2-3, then rejects 3-0 and 0-2 because their endpoints are already connected.

If the graph is disconnected the algorithm produces a minimum spanning *forest*: the “Disconnected” preset has 3 components and 3 edges.

The proof is the cut property: when the lightest remaining edge joins two components, it is the lightest edge across the cut separating one of them from everything else, so it is safe.

1// edges[i] = {u, v, weight}; returns the total weight of a minimum spanning forest
2static int kruskal(int n, int[][] edges) {
3    int[][] e = edges.clone();
4    Arrays.sort(e, Comparator.comparingInt(x -> x[2]));
5    int[] parent = new int[n];
6    for (int i = 0; i < n; i++) parent[i] = i;
7    int total = 0;
8    for (int[] edge : e) {
9        int a = find(parent, edge[0]), b = find(parent, edge[1]);
10        if (a != b) { parent[a] = b; total += edge[2]; }     // different components: the edge is safe
11    }
12    return total;
13}
14
15static int find(int[] parent, int x) {
16    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }   // path halving
17    return x;
18}

1static int kruskal(int n, int[][] edges) {                 // edges[i] = {u, v, weight}
2    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));  // lightest first
3    int[] parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i;
4    int total = 0;
5    for (int[] e : edges) {
6        int a = find(parent, e[0]), b = find(parent, e[1]);  // component leaders of the two ends
7        if (a != b) { parent[a] = b; total += e[2]; }        // different components: keep the edge, merge them
8    }                                                         // same component: the edge would close a cycle, skip it
9    return total;
10}

Prim's algorithm grows one tree from a start vertex. A min-heap holds the edges leaving the tree; repeatedly take the lightest one whose far end is not yet in the tree, add that vertex, and push its edges. On the “Classic” graph it also reaches total weight 11, the same as Kruskal's, although the edges may be chosen in a different order.

Unlike Kruskal's, Prim's grows a single tree, so on a disconnected graph it spans only the start vertex's component (“Unreachable vertices” builds a tree of 2 vertices). With a binary heap the cost is O(E log V); with an adjacency matrix and a linear scan for the minimum it is O(V²), which is better for dense graphs.

1// adj.get(u) holds {v, weight}; returns the weight of the tree containing vertex 0
2static int prim(List<List<int[]>> adj) {
3    int n = adj.size();
4    boolean[] inTree = new boolean[n];
5    PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(x -> x[1]));   // {vertex, edge weight}
6    heap.add(new int[]{0, 0});
7    int total = 0;
8    while (!heap.isEmpty()) {
9        int[] cur = heap.poll();
10        if (inTree[cur[0]]) continue;                        // stale entry: the vertex joined by a lighter edge
11        inTree[cur[0]] = true;
12        total += cur[1];
13        for (int[] edge : adj.get(cur[0])) {
14            if (!inTree[edge[0]]) heap.add(new int[]{edge[0], edge[1]});
15        }
16    }
17    return total;
18}

1static int prim(int n, List<int[]>[] adj) {                // adj[u] = list of {v, weight}; grows the tree from vertex 0
2    int[] key = new int[n]; Arrays.fill(key, Integer.MAX_VALUE); key[0] = 0;   // cheapest known edge into the tree
3    boolean[] inTree = new boolean[n]; int total = 0;
4    for (int step = 0; step < n; step++) {
5        int u = -1;
6        for (int v = 0; v < n; v++) if (!inTree[v] && (u == -1 || key[v] < key[u])) u = v;   // closest vertex outside the tree
7        if (key[u] == Integer.MAX_VALUE) break;               // nothing connects to the rest: it is unreachable
8        inTree[u] = true; total += key[u];
9        for (int[] e : adj[u]) if (!inTree[e[0]] && e[1] < key[e[0]]) key[e[0]] = e[1];   // offer cheaper connections
10    }
11    return total;
12}

Dijkstra's algorithm finds shortest paths from one source when every edge weight is nonnegative. Keep a tentative distance per vertex; repeatedly **settle** the unsettled vertex with the smallest distance, and relax its outgoing edges. The greedy claim is that a settled vertex's distance is final.

Why: any other path to the settled vertex v must leave the settled set through an edge to some vertex u that is not settled, and u's distance is already at least v's (v was the smallest), so adding further nonnegative edges cannot make that path shorter. The “Non-negative weights” preset ends with distances [0, 3, 1, 4], matching a Bellman-Ford reference run inside the animation.

1// adj.get(u) holds {v, weight}, all weights >= 0
2static int[] dijkstra(List<List<int[]>> adj, int source) {
3    int n = adj.size();
4    int[] dist = new int[n];
5    Arrays.fill(dist, Integer.MAX_VALUE);
6    dist[source] = 0;
7    PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(x -> x[1]));   // {vertex, distance}
8    heap.add(new int[]{source, 0});
9    while (!heap.isEmpty()) {
10        int[] cur = heap.poll();
11        if (cur[1] > dist[cur[0]]) continue;                 // stale entry
12        for (int[] edge : adj.get(cur[0])) {
13            int nd = cur[1] + edge[1];
14            if (nd < dist[edge[0]]) { dist[edge[0]] = nd; heap.add(new int[]{edge[0], nd}); }
15        }
16    }
17    return dist;
18}

1static int[] dijkstra(int n, List<int[]>[] adj, int src) {  // adj[u] = list of {v, weight}
2    int[] dist = new int[n]; Arrays.fill(dist, INF); dist[src] = 0;
3    boolean[] done = new boolean[n];
4    for (int step = 0; step < n; step++) {
5        int u = -1;
6        for (int v = 0; v < n; v++) if (!done[v] && dist[v] < INF && (u == -1 || dist[v] < dist[u])) u = v;   // closest unsettled vertex
7        if (u == -1) break;
8        done[u] = true;                                       // final: valid only when no edge is negative
9        for (int[] e : adj[u]) if (!done[e[0]] && dist[u] + e[1] < dist[e[0]]) dist[e[0]] = dist[u] + e[1];   // relax
10    }
11    return dist;
12}

The 'settled means final' argument needs every edge weight to be nonnegative. With a negative edge, a longer path through unsettled vertices can still become shorter. The “Negative edge: Dijkstra is wrong” preset has edges 0→1 of weight 2, 0→2 of weight 3, 2→1 of weight -2 and 1→3 of weight 1. The textbook version settles vertex 1 at distance 2 before it can learn that going through vertex 2 costs only 3 - 2 = 1, and reports distances [0, 2, 3, 3] where the correct answer is [0, 1, 3, 2].

The heap-based code above happens to repair this particular case by re-pushing vertex 1 when a shorter distance appears, but then vertices can be processed many times and the O((V + E) log V) bound is lost. The animation shows the textbook version that settles each vertex once, and that version is simply wrong. Bellman-Ford handles negative weights by relaxing every edge V - 1 times, and detects negative cycles with one more pass.

Some negative-edge graphs still work by luck (the “Negative edge that happens to work” preset). A test that passes proves nothing about the algorithm's guarantee.

1// Bellman-Ford: edges[i] = {u, v, weight}; returns null if a negative cycle is reachable from the source
2static long[] bellmanFord(int n, int[][] edges, int source) {
3    long INF = Long.MAX_VALUE / 4;
4    long[] dist = new long[n];
5    Arrays.fill(dist, INF);
6    dist[source] = 0;
7    for (int round = 1; round < n; round++) {
8        boolean changed = false;
9        for (int[] e : edges) {
10            if (dist[e[0]] < INF && dist[e[0]] + e[2] < dist[e[1]]) { dist[e[1]] = dist[e[0]] + e[2]; changed = true; }
11        }
12        if (!changed) break;
13    }
14    for (int[] e : edges) {
15        if (dist[e[0]] < INF && dist[e[0]] + e[2] < dist[e[1]]) return null;   // still improving: negative cycle
16    }
17    return dist;
18}

1static int[] dijkstra(int n, List<int[]>[] adj, int src) {  // adj[u] = list of {v, weight}
2    int[] dist = new int[n]; Arrays.fill(dist, INF); dist[src] = 0;
3    boolean[] done = new boolean[n];
4    for (int step = 0; step < n; step++) {
5        int u = -1;
6        for (int v = 0; v < n; v++) if (!done[v] && dist[v] < INF && (u == -1 || dist[v] < dist[u])) u = v;   // closest unsettled vertex
7        if (u == -1) break;
8        done[u] = true;                                       // final: valid only when no edge is negative
9        for (int[] e : adj[u]) if (!done[e[0]] && dist[u] + e[1] < dist[e[0]]) dist[e[0]] = dist[u] + e[1];   // relax
10    }
11    return dist;
12}