维基百科普里姆算法
图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
描述 从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图所有顶点。输入：一个加权连通图，其顶点集合为V, 边集合为E.初始化：Vnew = {x}, x为顶点集合V中任一节点（起始点），Enew = {}。重复以下步骤 直到 Vnew = V 在集合E中选取权值最小的边（u,v）,其中u 是集合Vnew 中元素，v 则是 V中尚未添加到Vnew 的顶点，如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）； 将v加入Vnew 中，将（u, v）加入集合Enew中;输出：使用集合Vnew和Enew来描述所得到的最小生成树。JAVA 代码实现
public class MyPrim { public static List<Vertex> vertexList = new ArrayList<>();//结点集，即V集合 public static List<Edge> edgeList = new ArrayList<>();//边集，即E集合 public static List<Vertex> newVertexList = new ArrayList<>();//已访问结点集，也就是Vnew结合 //构造图 private static void buildGraph() { Vertex v1 = new Vertex("v1"); vertexList.add(v1); Vertex v2 = new Vertex("v2"); vertexList.add(v2); Vertex v3 = new Vertex("v3"); vertexList.add(v3); Vertex v4 = new Vertex("v4"); vertexList.add(v4); Vertex v5 = new Vertex("v5"); vertexList.add(v5); Vertex v6 = new Vertex("v6"); vertexList.add(v6); Vertex v7 = new Vertex("v7"); vertexList.add(v7); addEdge(v1, v2, 4); addEdge(v1, v3, 5); addEdge(v2, v4, 1); addEdge(v2, v6, 2); addEdge(v3, v6, 6); addEdge(v3, v7, 4); addEdge(v4, v5, 8); addEdge(v4, v6, 3); addEdge(v5, v7, 9); } public static void addEdge(Vertex start, Vertex end, int weight) { Edge e = new Edge(start, end, weight); edgeList.add(e); } public static void main(String[] args) { prim(); } public static void prim() { buildGraph(); Vertex startVertex = vertexList.get(0); newVertexList.add(startVertex);//将起点加入到newVertexList中 //遍历n次,每次找出一个最小生成树结点 for (int i = 0; i < vertexList.size() - 1; i++) { Vertex temp = new Vertex(startVertex.name); Edge tempEdge = new Edge(startVertex, startVertex, 1000); //依次遍历newVertexList节点，找出start在newVertexList中，end在非newVertexList中的最小边，将end加入到newVertexList中 for (Vertex vertex : newVertexList) { for (Edge edge : edgeList) //遍历边，找出权值最小的边 { if (edge.start == vertex && !containsVertex(edge.end)) { if(edge.weight < tempEdge.weight){ temp = edge.end; tempEdge = edge; } } } } newVertexList.add(temp); } for (Vertex newVertex:newVertexList) { System.out.println(newVertex.name); } } public static boolean containsVertex(Vertex vertex) { for (Vertex newVertex : newVertexList) { if(newVertex.name.equals(vertex.name)){ return true; } } return false; } } class Vertex { String name; Vertex(String name) { this.name = name; } } class Edge { Vertex start; Vertex end; int weight; Edge(Vertex start, Vertex end, int weight) { this.start = start; this.end = end; this.weight = weight; } }