Minimum Spanning Trees

In graph theory, a minimum spanning tree (MST) is a spanning tree of a weighted connected graph that has the minimum possible weight. A spanning tree is a subgraph of a graph that includes all the vertices and is itself a tree.

Minimum spanning trees have various applications, especially in network design, where the goal is to minimize the cost to connect a set of nodes. For example, consider a scenario where you need to connect a set of cities with minimal cost, where each city represents a vertex and the cost to connect two cities represents the weight of an edge.

There are several algorithms to find the minimum spanning tree of a graph, including:

1. Prim's Algorithm

   • It starts with an arbitrary vertex and keeps adding the vertex with the minimum weight edge until all vertices are included in the spanning tree.
   • The key idea is to maintain a set of vertices already included in the minimum spanning tree (MST) and a set of vertices not yet included.
   • It works on connected, undirected, and weighted graphs.

2. Kruskal's Algorithm

   • It starts with the empty spanning tree and keeps adding the edge with the minimum weight until all vertices are included and the graph becomes connected.
   • The key idea is to sort the edges in increasing order of their weight and add the next edge to the spanning tree if it does not form a cycle.
   • It works on connected, undirected, and weighted graphs.

The choice of algorithm depends on the specific requirements and characteristics of the graph. Prim's algorithm is efficient for dense graphs, while Kruskal's algorithm works well for sparse graphs.

Here's an example of implementing Prim's Algorithm to find the minimum spanning tree of a graph:

1<`syntaxhighlight lang="java">
2import java.util.*;
3
4class Graph {
5    // Implement the Graph data structure and the constructors, addEdge() method, etc.
6
7    public void primMST() {
8        // Initialize the variables and data structures
9
10        while (/* There are vertices not included in MST */) {
11            // Find the vertex with the minimum weight edge
12
13            // Add the vertex to MST and update the data structures
14        }
15
16        // Print the minimum spanning tree
17    }
18}
19
20public class MinimumSpanningTrees {
21    public static void main(String[] args) {
22        // Create a graph object and add the edges
23
24        // Call the primMST() method to find the minimum spanning tree
25    }
26}
27</syntaxhighlight>`

xxxxxxxxxx

}

import java.util.*;

​

class Graph {

    private int v;

    private List<List<Pair<Integer, Integer>>>> adj;

​

    public Graph(int vertices) {

        v = vertices;

        adj = new ArrayList<>(v);

        for (int i = 0; i < v; i++) {

            adj.add(new ArrayList<>());

        }

    }

​

    public void addEdge(int src, int dest, int weight) {

        adj.get(src).add(new Pair<>(dest, weight));

        adj.get(dest).add(new Pair<>(src, weight));

    }

​

    public void primMST() {

        int[] key = new int[v];

        Arrays.fill(key, Integer.MAX_VALUE);

​

        boolean[] mstSet = new boolean[v];

​

        int[] parent = new int[v];

        parent[0] = -1;

​

        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(v, Comparator.comparingInt(Pair::getValue));