Advanced Graph Algorithms· 25 min

Kruskal's MST

Cheapest edges first, skip cycles with Union-Find

Setup

Step 1 / 18

Current step

1 / 18

Sort all 8 edges by weight: [DE:1, BC:2, AC:3, AB:4, BD:5, CE:6, DF:7, EF:8]. Greedily take the cheapest edge that doesn't form a cycle.

Step log

Considering
In MST
Rejected (cycle)
kruskal_mst.java
1import java.util.*;
2 
3public class Main {
4    record Edge(int from, int to, int weight) {}
5 
6    static class DSU {
7        private final int[] parent;
8        DSU(int size) { parent = new int[size]; for (int i = 0; i < size; i++) parent[i] = i; }
9        int find(int value) { return parent[value] == value ? value : (parent[value] = find(parent[value])); }
10        boolean union(int a, int b) {
11            int rootA = find(a), rootB = find(b);
12            if (rootA == rootB) return false;
13            parent[rootB] = rootA;
14            return true;
15        }
16    }
17 
18    public static List<Edge> kruskal(int vertices, List<Edge> edges) {
19        edges.sort(Comparator.comparingInt(Edge::weight));
20        DSU dsu = new DSU(vertices);
21        List<Edge> mst = new ArrayList<>();
22        for (Edge edge : edges) if (dsu.union(edge.from(), edge.to())) mst.add(edge);
23        return mst;
24    }
25 
26}
● Java
Time
O(E log E)
MST edges
0/5
MST weight
0
Edges total
8
D–E:1B–C:2A–C:3A–B:4B–D:5C–E:6D–F:7E–F:8
46 / 46