编辑代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class PrimMST {

    // 图的顶点类
    static class Vertex {
        public String name;
        public int distance = Integer.MAX_VALUE;
        public Vertex parent = null;

        public Vertex(String name) {
            this.name = name;
        }
    }

    // 图的边类
    static class Edge {
        public Vertex from;
        public Vertex to;
        public int weight;

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

    // 图类
    static class Graph {
        private Map<String, Vertex> vertices = new HashMap<>();
        private List<Edge> edges = new ArrayList<>();

        // 添加顶点
        public void addVertex(String name) {
            vertices.put(name, new Vertex(name));
        }

        // 添加边
        public void addEdge(String from, String to, int weight) {
            Vertex vFrom = vertices.get(from);
            Vertex vTo = vertices.get(to);
            edges.add(new Edge(vFrom, vTo, weight));
        }

        // 使用 Prim 算法构建最小生成树
        public List<Edge> getMST() {
            List<Edge> mst = new ArrayList<>();
            Set<Vertex> visited = new HashSet<>();

            // 从第一个顶点开始
            Vertex start = vertices.values().iterator().next();
            start.distance = 0;

            // 循环直到所有顶点都被访问过
            while (visited.size() < vertices.size()) {
                // 找到距离最小的未访问顶点
                Vertex minVertex = findMinDistanceVertex(visited);

                // 将该顶点加入到访问过的顶点集中
                visited.add(minVertex);

                // 如果该顶点有父节点，则将连接它们的边加入到最小生成树中
                if (minVertex.parent != null) {
                    mst.add(new Edge(minVertex.parent, minVertex, minVertex.distance));
                }

                // 更新相邻顶点的距离
                updateDistances(minVertex, visited);
            }

            return mst;
        }

        // 找到距离最小的未访问顶点
        private Vertex findMinDistanceVertex(Set<Vertex> visited) {
            Vertex minVertex = null;
            int minDistance = Integer.MAX_VALUE;
            for (Vertex v : vertices.values()) {
                if (!visited.contains(v) && v.distance < minDistance) {
                    minVertex = v;
                    minDistance = v.distance;
                }
            }
            return minVertex;
        }

        // 更新相邻顶点的距离
        private void updateDistances(Vertex vertex, Set<Vertex> visited) {
            for (Edge edge : edges) {
                if (edge.from == vertex && !visited.contains(edge.to) && edge.weight < edge.to.distance) {
                    edge.to.distance = edge.weight;
                    edge.to.parent = vertex;
                }
            }
        }
    }

    public static void main(String[] args) {
        // 创建图
        Graph graph = new Graph();
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addVertex("D");
        graph.addVertex("E");

        graph.addEdge("A", "B", 2);
        graph.addEdge("A", "C", 4);
        graph.addEdge("B", "C", 1);
        graph.addEdge("B", "D", 5);
        graph.addEdge("C", "E", 3);
        graph.addEdge("D", "E", 2);

        // 获取最小生成树
        List<Edge> mst = graph.getMST();

        // 打印最小生成树
        System.out.println("最小生成树：");
        for (Edge edge : mst) {
            System.out.println(edge.from.name + " - " + edge.to.name + " : " + edge.weight);
        }
    }
}