888914. Minimum Spanning Tree - Kruskal's Algorithm
Medium
Minimum Spanning Tree - Kruskal's Algorithm
Summary
Kruskal's algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a connected weighted graph. The MST is a subgraph that connects all vertices in the original graph with the minimum possible total edge weight. This problem involves implementing this algorithm using a disjoint set data structure to efficiently manage the edges and their connectivity.
Detailed Explanation
Kruskal's algorithm works by sorting all the edges in the graph by their weights, then iteratively adding the smallest-weighted edge that does not form a cycle with the already included edges. The algorithm terminates when the MST is formed, which is represented as a tree data structure.
Here is a step-by-step breakdown of the solution:
- Initialize an empty disjoint set
DSand a priority queuepqto store all the edges in the graph. - Sort the edges in the
pqbased on their weights. - While the
pqis not empty, do the following:- Extract the smallest-weighted edge from the
pq. - If the two vertices connected by this edge are not in the same set in
DS, merge the sets and add the edge to the MST.
- Extract the smallest-weighted edge from the
- The final MST is represented as a tree data structure.
Time Complexity Analysis
- Sorting edges: O(E log E) where E is the number of edges.
- Iterative process: O(E + V) where V is the number of vertices, since each edge and vertex are processed once. Total time complexity: O(E log E).
Space Complexity Analysis
- Disjoint set
DS: O(V) to store all the vertices. - Priority queue
pq: O(E) to store all the edges. Total space complexity: O(V + E).
Optimized Solutions
Java
public class Kruskal {
public static List<Edge> kruskalMST(Graph graph) {
List<Edge> mst = new ArrayList<>();
UnionFind uf = new UnionFind(graph.V());
PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> a.weight - b.weight);
for (Edge edge : graph.edges()) {
pq.add(edge);
}
while (!pq.isEmpty()) {
Edge edge = pq.poll();
int u = edge.u;
int v = edge.v;
if (uf.find(u) != uf.find(v)) {
mst.add(edge);
uf.union(u, v);
}
}
return mst;
}
static class UnionFind {
int[] parent;
int[] rank;
public UnionFind(int V) {
parent = new int[V];
rank = new int[V];
for (int i = 0; i < V; i++) {
parent[i] = i;
rank[i] = 0;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
}
static class Edge implements Comparable<Edge> {
int u;
int v;
int weight;
public Edge(int u, int v, int weight) {
this.u = u;
this.v = v;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.weight, o.weight);
}
}
}