Minimum Spanning Tree Algorithms

Understanding Minimum Spanning Trees

A Minimum Spanning Tree (MST) of a weighted undirected graph is a subset of its edges that connects all the vertices together, without any cycles, and with the minimum possible total edge weight.

When working with graphs, it's often necessary to find a way to connect all nodes with the least cost possible, whether that cost is distance in a network or weight in a cost graph. Here, we explore two powerful algorithms that help achieve this: Kruskal's and Prim's.

Kruskal's Algorithm

Kruskal's algorithm builds the MST by continually adding edges to the spanning tree in order of their weight until all vertices are connected. It operates using the Disjoint Set (Union-Find) to detect cycles.

Step-by-step Procedure

1. Sort All Edges: Start by sorting all the edges in non-decreasing order of their weights.

2. Initialize a Forest: Create a forest, which is a set of trees. Each vertex is a separate component.

3. Pick the Smallest Edge: Iterate through the edges, and for each edge, check if it forms a cycle with the already chosen edges.

   • If it doesn’t form a cycle, include it in the result and union the two vertices.
   • If it does form a cycle, discard it.

4. Stop When the MST is Complete: The process continues until there are V - 1 edges in the MST, where V is the number of vertices in the graph.

Java Implementation of Kruskal's Algorithm

import java.util.*;

class Edge implements Comparable<Edge> {
    int source, destination, weight;

    Edge(int source, int destination, int weight) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}

class DisjointSet {
    private int[] parent, rank;

    DisjointSet(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    int find(int u) {
        if (u != parent[u]) {
            parent[u] = find(parent[u]);
        }
        return parent[u];
    }

    void union(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            if (rank[rootU] > rank[rootV]) {
                parent[rootV] = rootU;
            } else if (rank[rootU] < rank[rootV]) {
                parent[rootU] = rootV;
            } else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }
}

public class KruskalMST {
    public static void kruskal(int vertices, List<Edge> edges) {
        Collections.sort(edges);
        DisjointSet ds = new DisjointSet(vertices);
        List<Edge> mst = new ArrayList<>();

        for (Edge edge : edges) {
            if (ds.find(edge.source) != ds.find(edge.destination)) {
                ds.union(edge.source, edge.destination);
                mst.add(edge);
            }
        }

        // Print the resulting MST
        for (Edge edge : mst) {
            System.out.println(edge.source + " -- " + edge.destination + " == " + edge.weight);
        }
    }

    public static void main(String[] args) {
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 10));
        edges.add(new Edge(0, 2, 6));
        edges.add(new Edge(0, 3, 5));
        edges.add(new Edge(1, 3, 15));
        edges.add(new Edge(2, 3, 4));

        int vertices = 4; // Number of vertices in the graph
        kruskal(vertices, edges);
    }
}

Prim's Algorithm

Prim's algorithm finds the MST by expanding the tree one edge at a time, starting from any arbitrary vertex, and choosing the smallest edge that expands the spanning tree.

Step-by-step Procedure

1. Start from an Arbitrary Node: Choose any node to start from and mark it as part of the MST.

2. Priority Queue: Use a priority queue to select the minimum weight edge that connects a vertex in the MST with a vertex outside it.

3. Select the Minimum Weight Edge: Expand the tree by adding the selected edge to the MST.

4. Continue: Repeat the process until all vertices are included in the MST.

Java Implementation of Prim's Algorithm

import java.util.*;

public class PrimMST {
    static class Edge {
        int vertex, weight;

        Edge(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }
    }

    public static void prim(int vertices, List<List<Edge>> graph) {
        boolean[] inMST = new boolean[vertices];
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.weight));
        pq.add(new Edge(0, 0)); // Starting from vertex 0

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            if (inMST[edge.vertex]) continue; // Already in MST, skip
            inMST[edge.vertex] = true; // Mark vertex as included

            System.out.println(edge.vertex + " (weight: " + edge.weight + ")");
            for (Edge neighbor : graph.get(edge.vertex)) {
                if (!inMST[neighbor.vertex]) {
                    pq.add(new Edge(neighbor.vertex, neighbor.weight));
                }
            }
        }
    }

    public static void main(String[] args) {
        int vertices = 5;
        List<List<Edge>> graph = new ArrayList<>(vertices);
        
        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }
        
        graph.get(0).add(new Edge(1, 2));
        graph.get(0).add(new Edge(3, 6));
        graph.get(1).add(new Edge(2, 3));
        graph.get(1).add(new Edge(3, 8));
        graph.get(1).add(new Edge(4, 5));
        graph.get(2).add(new Edge(4, 7));
        graph.get(3).add(new Edge(4, 9));

        prim(vertices, graph);
    }
}

Time Complexity

• Kruskal's Algorithm: The time complexity is O(E log E), where E is the number of edges, mainly due to the sorting step. The union-find operations can be done in almost constant time.

• Prim's Algorithm: The time complexity is O(E log V) if using a priority queue, where V is the number of vertices.

Choosing which algorithm to use depends largely on the specific scenario. If you're working with dense graphs, Prim's algorithm is usually better because it operates with edges more efficiently. For sparse graphs, Kruskal's algorithm may be the better choice as it doesn't rely specifically on adjacency information.

Both of these algorithms are vital tools in a computer scientist's toolkit and are commonly asked about in interviews, so familiarity with both is essential.