Prim算法

Prim算法是一种用于在加权连通图中构建最小生成树的贪心算法。以下是Prim算法的Java代码示例，用于构建最小生成树：

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

class Edge implements Comparable<Edge> {
    int to;
    int weight;

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

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

public class PrimAlgorithm {

    public static List<Edge> primMST(List<List<Edge>> graph) {
        int n = graph.size();
        List<Edge> minimumSpanningTree = new ArrayList<>();
        boolean[] visited = new boolean[n];
        
        PriorityQueue<Edge> minHeap = new PriorityQueue<>();
        minHeap.offer(new Edge(0, 0));  // Start from the first node

        while (!minHeap.isEmpty()) {
            Edge currentEdge = minHeap.poll();
            int currentNode = currentEdge.to;

            if (visited[currentNode]) {
                continue;
            }
            visited[currentNode] = true;

            minimumSpanningTree.add(currentEdge);

            for (Edge neighbor : graph.get(currentNode)) {
                if (!visited[neighbor.to]) {
                    minHeap.offer(neighbor);
                }
            }
        }

        return minimumSpanningTree;
    }

    public static void main(String[] args) {
        int n = 5;  // Number of nodes
        List<List<Edge>> graph = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // Add edges to the graph
        graph.get(0).add(new Edge(1, 2));
        graph.get(0).add(new Edge(2, 3));
        graph.get(1).add(new Edge(2, 1));
        graph.get(1).add(new Edge(3, 4));
        graph.get(2).add(new Edge(4, 5));

        List<Edge> minimumSpanningTree = primMST(graph);

        System.out.println("Minimum Spanning Tree:");
        for (Edge edge : minimumSpanningTree) {
            System.out.println(edge.to + " - " + edge.weight);
        }
    }
}

在这个示例中，primMST 方法使用Prim算法构建了一个加权连通图的最小生成树。算法使用了最小堆（PriorityQueue）来选择边的权重最小的节点，从而逐步构建最小生成树。

请注意，这个示例是基于邻接表表示的图的Prim算法，实际应用中可能需要根据具体的图表示方式进行适当的修改。