微信
支付宝
# 7.6 普利姆(Prim)算法和克鲁斯卡尔(Kruskal)算法 #### 一. 定义 ##### 1.最小生成树(Minimum Cost Spanning Tree) 最小生成树(Minimum Cost Spanning Tree)，简称MST。给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树 。其N个顶点，一定有N-1条边，且包含全部顶点。求最小生成树的算法主要是\*\*普里姆算法\*\*和\*\*克鲁斯卡尔算法\*\*。  ##### 2.普利姆(Prim)算法 普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图。 \* 设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合 。 \* 若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，标记顶点v的visited\[u\]=1。 \* 若集合U中顶点ui与集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边（ui,vj）加入集合D中，标记visited\[vj\]=1。 \* 重复步骤2，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边。 ##### 3.克鲁斯卡尔(Kruskal)算法 克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。基本思想是按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。 具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。 #### 二. 应用场景 ##### 1.修路问题  有胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在需要修路把7个村庄连通各个村庄的距离用边线表示(权) ，比如 A -- B 距离 5公里。 问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短? 思路: 将10条边，连接即可，但是总的里程数不是最小。修路问题本质就是就是最小生成树问题，正确的思路，就是尽可能的选择少的路线，并且每条路线最小，保证总里程数最少。 ##### 2.公交站问题  有北京有新增7个站点(A, B, C, D, E, F, G) ，现在需要修路把7个站点连通，各个站点的距离用边线表示(权) ，比如 A -- B 距离 12公里。 问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短? #### 三. 代码实现 \`\`\`java /\*\* \* desc 普利姆算法解决修路问题 \* @author GreyPigeon mail:2371849349@qq.com \* @since 2024-02-20-21:19 \*\*/ public class PrimAlgorithm { public static void main(String\[\] args) { //测试看看图是否创建ok char\[\] data = new char\[\]{'A','B','C','D','E','F','G'}; int verxs = data.length; //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通 int \[\]\[\]weight=new int\[\]\[\]{ {10000,5,7,10000,10000,10000,2}, {5,10000,10000,9,10000,10000,3}, {7,10000,10000,10000,8,10000,10000}, {10000,9,10000,10000,10000,4,10000}, {10000,10000,8,10000,10000,5,4}, {10000,10000,10000,4,5,10000,6}, {2,3,10000,10000,4,6,10000},}; //创建MGraph对象 MGraph graph = new MGraph(verxs); //创建一个MinTree对象 MinTree minTree = new MinTree(); minTree.createGraph(graph, verxs, data, weight); //输出 minTree.showGraph(graph); //测试普利姆算法 minTree.prim(graph, 0); } } //创建最小生成树-\>村庄的图 class MinTree { /\*\* \* 创建图的邻接矩阵 \* @param graph 图对象 \* @param verxs 图对应的顶点个数 \* @param data 图的各个顶点的值 \* @param weight 图的邻接矩阵 \*/ public void createGraph(MGraph graph, int verxs, char data\[\], int\[\]\[\] weight) { int i, j; for(i = 0; i \< verxs; i++) {//顶点 graph.data\[i\] = data\[i\]; for(j = 0; j \< verxs; j++) { graph.weight\[i\]\[j\] = weight\[i\]\[j\]; } } } //显示图的邻接矩阵 public void showGraph(MGraph graph) { for(int\[\] link: graph.weight) { System.out.println(Arrays.toString(link)); } } /\*\* \* 编写prim算法，得到最小生成树 \* @param graph 图 \* @param v 表示从图的第几个顶点开始生成'A'-\>0 'B'-\>1... \*/ public void prim(MGraph graph, int v) { //visited\[\] 标记结点(顶点)是否被访问过 int visited\[\] = new int\[graph.verxs\]; //visited\[\] 默认元素的值都是0, 表示没有访问过 // for(int i =0; i 权值:" + minWeight); //将当前这个结点标记为已经访问 visited\[h2\] = 1; //minWeight 重新设置为最大值 10000 minWeight = 10000; } } } class MGraph { int verxs; //表示图的节点个数 char\[\] data;//存放结点数据 int\[\]\[\] weight; //存放边，就是我们的邻接矩阵 public MGraph(int verxs) { this.verxs = verxs; data = new char\[verxs\]; weight = new int\[verxs\]\[verxs\]; } } \`\`\` \`\`\`java /\*\* \* desc 克鲁斯卡尔算法实现公交问题 \* @author GreyPigeon mail:2371849349@qq.com \* @since 2024-02-21-18:19 \*\*/ public class KruskalCase { private int edgeNum; //边的个数 private char\[\] vertexs; //顶点数组 private int\[\]\[\] matrix; //邻接矩阵 //使用 INF 表示两个顶点不能连通 private static final int INF = Integer.MAX_VALUE; public static void main(String\[\] args) { char\[\] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; //克鲁斯卡尔算法的邻接矩阵 int matrix\[\]\[\] = { /\*A\*//\*B\*//\*C\*//\*D\*//\*E\*//\*F\*//\*G\*/ /\*A\*/ { 0, 12, INF, INF, INF, 16, 14}, /\*B\*/ { 12, 0, 10, INF, INF, 7, INF}, /\*C\*/ { INF, 10, 0, 3, 5, 6, INF}, /\*D\*/ { INF, INF, 3, 0, 4, INF, INF}, /\*E\*/ { INF, INF, 5, 4, 0, 2, 8}, /\*F\*/ { 16, 7, 6, INF, 2, 0, 9}, /\*G\*/ { 14, INF, INF, INF, 8, 9, 0}}; //去测试其它的邻接矩阵，结果都可以得到最小生成树. //创建KruskalCase 对象实例 KruskalCase kruskalCase = new KruskalCase(vertexs, matrix); //输出构建的 kruskalCase.print(); kruskalCase.kruskal(); } //构造器 public KruskalCase(char\[\] vertexs, int\[\]\[\] matrix) { //初始化顶点数和边的个数 int vlen = vertexs.length; //初始化顶点, 复制拷贝的方式 this.vertexs = new char\[vlen\]; for(int i = 0; i \< vertexs.length; i++) { this.vertexs\[i\] = vertexs\[i\]; } //初始化边, 使用的是复制拷贝的方式 this.matrix = new int\[vlen\]\[vlen\]; for(int i = 0; i \< vlen; i++) { for(int j= 0; j \< vlen; j++) { this.matrix\[i\]\[j\] = matrix\[i\]\[j\]; } } //统计边的条数 for(int i =0; i \< vlen; i++) { for(int j = i+1; j \< vlen; j++) { if(this.matrix\[i\]\[j\] != INF) { edgeNum++; } } } } public void kruskal() { int index = 0; //表示最后结果数组的索引 int\[\] ends = new int\[edgeNum\]; //用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点 //创建结果数组, 保存最后的最小生成树 EData\[\] rets = new EData\[edgeNum\]; //获取图中 所有的边的集合 ， 一共有12边 EData\[\] edges = getEdges(); System.out.println("图的边的集合=" + Arrays.toString(edges) + " 共"+ edges.length); //12 //按照边的权值大小进行排序(从小到大) sortEdges(edges); //遍历edges 数组，将边添加到最小生成树中时，判断是准备加入的边否形成了回路，如果没有，就加入 rets, 否则不能加入 for(int i=0; i \< edgeNum; i++) { //获取到第i条边的第一个顶点(起点) int p1 = getPosition(edges\[i\].start); //p1=4 //获取到第i条边的第2个顶点 int p2 = getPosition(edges\[i\].end); //p2 = 5 //获取p1这个顶点在已有最小生成树中的终点 int m = getEnd(ends, p1); //m = 4 //获取p2这个顶点在已有最小生成树中的终点 int n = getEnd(ends, p2); // n = 5 //是否构成回路 if(m != n) { //没有构成回路 ends\[m\] = n; // 设置m 在"已有最小生成树"中的终点 \[0,0,0,0,5,0,0,0,0,0,0,0\] rets\[index++\] = edges\[i\]; //有一条边加入到rets数组 } } // 。 //统计并打印 "最小生成树", 输出 rets System.out.println("最小生成树为"); for(int i = 0; i \< index; i++) { System.out.println(rets\[i\]); } } //打印邻接矩阵 public void print() { System.out.println("邻接矩阵为: \\n"); for(int i = 0; i \< vertexs.length; i++) { for(int j=0; j \< vertexs.length; j++) { System.out.printf("%12d", matrix\[i\]\[j\]); } System.out.println();//换行 } } /\*\* \* 功能：对边进行排序处理, 冒泡排序 \* @param edges 边的集合 \*/ private void sortEdges(EData\[\] edges) { for(int i = 0; i \< edges.length - 1; i++) { for(int j = 0; j \< edges.length - 1 - i; j++) { if(edges\[j\].weight \> edges\[j+1\].weight) {//交换 EData tmp = edges\[j\]; edges\[j\] = edges\[j+1\]; edges\[j+1\] = tmp; } } } } /\*\* \* \* @param ch 顶点的值，比如'A','B' \* @return 返回ch顶点对应的下标，如果找不到，返回-1 \*/ private int getPosition(char ch) { for(int i = 0; i \< vertexs.length; i++) { if(vertexs\[i\] == ch) {//找到 return i; } } //找不到,返回-1 return -1; } /\*\* \* 功能: 获取图中边，放到EData\[\] 数组中，后面我们需要遍历该数组 \* 是通过matrix 邻接矩阵来获取 \* EData\[\] 形式 \[\['A','B', 12\], \['B','F',7\], .....\] \* @return \*/ private EData\[\] getEdges() { int index = 0; EData\[\] edges = new EData\[edgeNum\]; for(int i = 0; i \< vertexs.length; i++) { for(int j=i+1; j = " + weight + "\]"; } } \`\`\`
本文是原创文章，采用 CC BY-NC-ND 4.0 协议，完整转载请注明来自 Veylor
最近发布
![常用SQL]()
常用SQL
