How to implement the minimum spanning tree algorithm using java

How to use Java to implement the minimum spanning tree algorithm

The minimum spanning tree algorithm is a classic problem in graph theory, used to solve the minimum of a weighted connected graph spanning tree. This article will introduce how to use Java language to implement this algorithm and provide specific code examples.

1. Problem Description
   Given a connected graph G, in which each edge has a weight, it is required to find a minimum spanning tree T such that the sum of the weights of all edges in T is the smallest.
2. Prim algorithm
   Prim algorithm is a greedy algorithm used to solve the minimum spanning tree problem. Its basic idea is to start from a vertex and gradually expand the spanning tree, selecting the vertex closest to the existing spanning tree each time until all vertices are added to the spanning tree.

The following is a Java implementation example of Prim's algorithm:

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

class Edge implements Comparable<Edge> {
    int from;
    int to;
    int weight;
    
    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}

public class Prim {
    public static List<Edge> calculateMST(List<List<Edge>> graph) {
        int n = graph.size();
        boolean[] visited = new boolean[n];
        Queue<Edge> pq = new PriorityQueue<>();
        
        // Start from vertex 0
        int start = 0;
        visited[start] = true;
        for (Edge e : graph.get(start)) {
            pq.offer(e);
        }
        
        List<Edge> mst = new ArrayList<>();
        while (!pq.isEmpty()) {
            Edge e = pq.poll();
            int from = e.from;
            int to = e.to;
            int weight = e.weight;
            
            if (visited[to]) {
                continue;
            }
            
            visited[to] = true;
            mst.add(e);
            
            for (Edge next : graph.get(to)) {
                if (!visited[next.to]) {
                    pq.offer(next);
                }
            }
        }
        
        return mst;
    }
}

3. Kruskal algorithm
   Kruskal algorithm is also a greedy algorithm used to solve the minimum spanning tree problem. Its basic idea is to sort all the edges in the graph according to the weight from small to large, and then add them to the spanning tree in turn. When adding an edge, if the two endpoints of the edge do not belong to the same connected component, then these edges can be added to the spanning tree. The two endpoints merge into a connected component.

The following is a Java implementation example of Kruskal's algorithm:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Edge implements Comparable<Edge> {
    int from;
    int to;
    int weight;
    
    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}

public class Kruskal {
    public static List<Edge> calculateMST(List<Edge> edges, int n) {
        List<Edge> mst = new ArrayList<>();
        Collections.sort(edges);
        
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        for (Edge e : edges) {
            int from = e.from;
            int to = e.to;
            int weight = e.weight;
            
            int parentFrom = findParent(from, parent);
            int parentTo = findParent(to, parent);
            
            if (parentFrom != parentTo) {
                mst.add(e);
                parent[parentFrom] = parentTo;
            }
        }
        
        return mst;
    }
    
    private static int findParent(int x, int[] parent) {
        if (x != parent[x]) {
            parent[x] = findParent(parent[x], parent);
        }
        
        return parent[x];
    }
}

4. Example usage
   The following is a simple example usage:

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<List<Edge>> graph = new ArrayList<>();
        graph.add(new ArrayList<>());
        graph.add(new ArrayList<>());
        graph.add(new ArrayList<>());
        graph.add(new ArrayList<>());
        
        graph.get(0).add(new Edge(0, 1, 2));
        graph.get(0).add(new Edge(0, 2, 3));
        graph.get(1).add(new Edge(1, 0, 2));
        graph.get(1).add(new Edge(1, 2, 1));
        graph.get(1).add(new Edge(1, 3, 5));
        graph.get(2).add(new Edge(2, 0, 3));
        graph.get(2).add(new Edge(2, 1, 1));
        graph.get(2).add(new Edge(2, 3, 4));
        graph.get(3).add(new Edge(3, 1, 5));
        graph.get(3).add(new Edge(3, 2, 4));
        
        List<Edge> mst = Prim.calculateMST(graph);
        System.out.println("Prim算法得到的最小生成树：");
        for (Edge e : mst) {
            System.out.println(e.from + " -> " + e.to + "，权重：" + e.weight);
        }
        
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 2));
        edges.add(new Edge(0, 2, 3));
        edges.add(new Edge(1, 2, 1));
        edges.add(new Edge(1, 3, 5));
        edges.add(new Edge(2, 3, 4));
        
        mst = Kruskal.calculateMST(edges, 4);
        System.out.println("Kruskal算法得到的最小生成树：");
        for (Edge e : mst) {
            System.out.println(e.from + " -> " + e.to + "，权重：" + e.weight);
        }
    }
}

By running the above example program, you can get the following output:

Prim算法得到的最小生成树：
0 -> 1，权重：2
1 -> 2，权重：1
2 -> 3，权重：4
Kruskal算法得到的最小生成树：
1 -> 2，权重：1
0 -> 1，权重：2
2 -> 3，权重：4

The above is a specific code example of using Java to implement the minimum spanning tree algorithm. Through these sample codes, readers can better understand and learn the implementation process and principles of the minimum spanning tree algorithm. Hope this article is helpful to readers.

The above is the detailed content of How to implement the minimum spanning tree algorithm using java. For more information, please follow other related articles on the PHP Chinese website!