What is the Minimum Spanning Tree (MST) problem, and how do Kruskal’s and Prim’s algorithms solve it?

The Minimum Spanning Tree (MST) problem is a well-known graph problem that involves finding the minimum cost tree that spans all nodes in a given graph. In other words, the MST problem asks for the subset of edges in a graph that form a tree, connecting all the vertices while minimizing the sum of edge weights.

Kruskal’s algorithm and Prim’s algorithm are two popular algorithms for solving the MST problem.

Kruskal’s algorithm works by sorting all edges in ascending order of their weights and then adding them to the MST one by one, as long as the edge being added does not create a cycle. This is done by maintaining a set of disjoint subsets, initially containing each vertex as a separate subset. As each edge is considered, its endpoints are placed into the same subset if they are not already in the same set. If the endpoints are already in the same set, the edge would form a cycle and is discarded.

Here is an example implementation of Kruskal’s algorithm in Java:

public static List<Edge> kruskalMST(Graph g) {
    List<Edge> mst = new ArrayList<>();
    List<Edge> edges = new ArrayList<>(g.getEdges());
    Collections.sort(edges); // sort edges by weight
    DisjointSet ds = new DisjointSet(g.getVertices());

    for (Edge e : edges) {
        int u = e.getSource();
        int v = e.getDestination();
        int setU = ds.find(u);
        int setV = ds.find(v);
        if (setU != setV) { // check if adding edge creates a cycle
            mst.add(e);
            ds.union(setU, setV); // merge the two subsets
        }
    }
    return mst;
}

Prim’s algorithm, on the other hand, works by building the MST incrementally from a starting vertex, adding the minimum weight edge that connects the already visited vertices to the unvisited vertices in each iteration. This process continues until all vertices are visited.

Here is an example implementation of Prim’s algorithm in Java:

public static List<Edge> primMST(Graph g) {
    List<Edge> mst = new ArrayList<>();
    int[] parent = new int[g.getNumVertices()];
    int[] key = new int[g.getNumVertices()];
    boolean[] mstSet = new boolean[g.getNumVertices()];
    Arrays.fill(key, Integer.MAX_VALUE);
    key[0] = 0;
    parent[0] = -1;

    for (int i = 0; i < g.getNumVertices() - 1; i++) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;
        for (Edge e : g.getAdjacentEdges(u)) {
            int v = e.getDestination();
            if (!mstSet[v] && e.getWeight() < key[v]) {
                parent[v] = u;
                key[v] = e.getWeight();
            }
        }
    }

    for (int i = 1; i < g.getNumVertices(); i++) {
        mst.add(new Edge(parent[i], i, key[i]));
    }
    return mst;
}

private static int minKey(int[] key, boolean[] mstSet) {
    int min = Integer.MAX_VALUE, minIndex = -1;
    for (int i = 0; i < key.length; i++) {
        if (!mstSet[i] && key[i] < min) {
            min = key[i];
            minIndex = i;
        }
    }
    return minIndex;
}