最小生成树和普利姆算法及克鲁斯卡尔算法

2024-01-01 06:50
文章标签 算法 最小 生成 普利 卡尔 克鲁斯

本文主要是介绍最小生成树和普利姆算法及克鲁斯卡尔算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、最小生成树的介绍

最小生成树(Minimum Cost Spanning Tree)， 简称 MST。即给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树

在这里插入图片描述

  1. 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树
  2. N个顶点，一定有N-1条边
  3. 包含全部顶点
  4. 求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法

二、普利姆算法

普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图

2.1 普利姆算法的基本思路

  1. 设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合
  2. 若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，标记顶点v的visited[u]=1
  3. 若集合U中顶点ui与集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边（ui,vj）加入集合D中，标记visited[vj]=1
  4. 重复步骤②，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边

2.2 应用场景

有胜利乡有7个村庄(A, B, C, D, E, F, G)，现在需要修路把7个村庄连通 各个村庄的距离用边线表示(权)，比如 A – B 距离 5公里。问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?
在这里插入图片描述

基本步骤：

  1. 首先，约定 V 为所有顶点的集合；约定 TE 为最小生成树中边的集合，初始为空；约定 U 为最小生成树中边的顶点集合，初始为空。

  2. 选择从 A 点开始普里姆算法，则 U = { A }。
    在这里插入图片描述

  3. 找出所有与集合 U 中的顶点相连的权重最小的边作为最小生成树的边。此时集合 U 中只有一个 A顶点，在集合 V-U 中与 A 顶点相连的边有 <A，B>[5]、<A，C>[7]、<A，G>[2]。其中权重最小的边为 <A，G>[2]，因此我们选择其为最小生成树的一条边，然后将此边加入 TE 集合，将 G 顶点加入 U 集合。此时 TE = { <A，G> }，U = { A，G }。
    在这里插入图片描述

  4. 继续找出所有与集合 U 中顶点相连的权重最小的边作为生成树的边。此时集合 U = { A、G }，在顶点集合 V-U 中分别与顶点 A、C 相连的边有 <A、B>[5]、<A、C>[7]、<G、B>[3]、<G、E>[4]、<G、F>[6]。其中权重最小的边为 <G、B>[3]，因此我们选取其为最小生成树的边，加入 TE 集合，将顶点 B 加入 U 集合。此时 TE = { <A，G> ，<G，B> }，U = { A，G，B }。
    在这里插入图片描述

  5. 继续找出所有与集合 U 中顶点相连的权重最小的边作为生成树的边。此时集合 U = { A、G、B }，在顶点集合 V-U 中分别与顶点 A、C 相连的边有 <A、C>[7]、<G、E>[4]、<G、F>[6]、<B、D>[9]。其中权重最小的边为 <G、E>[4]，因此我们选取其为最小生成树的边，加入 TE 集合，将顶点 B 加入 U 集合。此时 TE = { <A，G> ，<G，B> ,<G、E>}，U = { A，G，B，E}。
    在这里插入图片描述

  6. 继续找出所有与集合 U 中顶点相连的权重最小的边作为生成树的边。此时集合 U = { A、G、B、E }，在顶点集合 V-U 中分别与顶点 A、C 相连的边有 <A、C>[7]、<E、C>[8]、<E、F>[5]、<G、F>[6]、<B、D>[9]。其中权重最小的边为 <E、F>[5]，因此我们选取其为最小生成树的边，加入 TE 集合，将顶点 B 加入 U 集合。此时 TE = { <A，G> ，<G，B> ,<G、E>，<E、F>}，U = { A，G，B，E，F}。
    在这里插入图片描述
    7.以此类推，最后得到的结果集为TE = { <A，G> ，<G，B> ，<G、E>，<E、F>，<F、D>，<A、C>}，U = { A，G，B，E，F，D，C}。至此，集合 U 等于了 V，也就是构造出了最小生成树，最后将所有权值加起来的结果得到25，说明至少要修路25公里，普里姆算法结束。
    在这里插入图片描述

2.3 代码实现

package algorithm.prim;import java.util.Arrays;public class PrimAlgorithm {public static void main(String[] args) {char[] data = new char[]{'A','B','C','D','E','F','G'};int verxes = data.length;int[][] weight = {  // 邻接矩阵，约定 10000 代表不连通/*A*//*B*//*C*//*D*//*E*//*F*//*G*//*A*/{10000,5,7,10000,10000,10000,2},/*B*/{5,10000,10000,9,10000,10000,3},/*C*/{7,10000,10000,10000,8,10000,10000},/*D*/{10000,9,10000,10000,10000,4,10000},/*E*/{10000,10000,8,10000,10000,5,4},/*F*/{10000,10000,10000,4,5,10000,6},/*G*/{2,3,10000,10000,4,6,10000}};Graph graph = new Graph(verxes);MinTree minTree = new MinTree();minTree.createGraph(graph,verxes,data,weight);minTree.showGraph(graph);//普利姆算法minTree.prim(graph,0);}
}//创建最小生成树
class MinTree{//创建图的邻接矩阵/**** @param graph 图对象* @param verxes    图对应的顶点个数* @param data  图各个顶点的值* @param weight    图的邻接矩阵*/public void createGraph(Graph graph,int verxes,char data[],int[][] weight){int i,j;for(i = 0;i < verxes;i++){graph.data[i] = data[i];for(j = 0;j < verxes;j++){graph.weight[i][j] = weight[i][j];}}}//显示图的邻接矩阵public void showGraph(Graph graph){for(int[] link:graph.weight){System.out.println(Arrays.toString(link));}}//编写普利姆算法public void prim(Graph graph,int vNum){int[] visited = new int[graph.verxes];//判断顶点有没有被访问过,默认为0visited[vNum] = 1;//h1和h2记录两个顶点的下标int h1 = -1;int h2 = -2;int minWeight = 10000;//将minweight初试成一个较大的数，之后替换为最小权值for(int k = 1; k < graph.verxes;k++){//有n个顶点，算法结束后会有n-1条边//确定每一次生成的子图，和哪个结点的距离最近for(int i = 0;i < graph.verxes;i++){//i结点表示被访问过的节点for(int j = 0;j < graph.verxes;j++){//j表示还没有被访问过的节点if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight){//替换minweightminWeight = graph.weight[i][j];h1 = i;h2 = j;}}}System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值：" + minWeight);//将当前找到的节点标记为已经访问visited[h2] = 1;//重置minweightminWeight = 10000;}}
}
class Graph{int verxes;//表示图的节点个数char[] data;//存放节点数据int[][] weight;//存放边，邻接矩阵public Graph(int verxes){this.verxes = verxes;data = new char[verxes];weight = new int[verxes][verxes];}
}

运行结果：
在这里插入图片描述

三、克鲁斯卡尔算法

3.1 克鲁斯卡尔算法的介绍

克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。其基本思想是按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路

首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止

3.2 应用场景

有北京有新增7个站点(A, B, C, D, E, F, G) ，现在需要修路把7个站点连通，各个站点的距离用边线表示(权) ，比如 A – B 距离 12公里。问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?
在这里插入图片描述
基本步骤：

在这里插入图片描述
最后形成一颗最小生成树，它包括的边依次是：<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>

Kruskal算法重点需要解决的两个问题

问题一 ： 对图的所有边按照权值大小进行排序。
问题二 ： 将边添加到最小生成树中时，怎么样判断是否形成了回路。

问题一，很好解决，采用排序算法进行排序即可。

问题二，处理方式是：记录顶点在”最小生成树”中的终点，顶点的终点是”在最小生成树中与它连通的最大顶点”。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。

卡鲁斯卡尔算法的实现最麻烦的就是实现如何判断新添加的边是否和已选择的边构成回路，为此，引入了终点的概念：所有顶点按照从小到大（一般指索引大小）的顺序排列好之后，某个顶点的终点就是 “与它连通的最大顶点”。

下面将以实现过程的第三步为例，具体讲解一下判断回路的思想
在这里插入图片描述

在将<E,F> <C,D> <D,E>加入到最小生成树R中之后，这几条边的顶点就都有了终点：

(01) C的终点是F。
(02) D的终点是F。
(03) E的终点是F。
(04) F的终点是F。

所以，通过分析虽然<C,E>是权值最小的边。 但是 C 和 E 的终点都是 F， 即它们的终点相同， 因此， 将<C,E>加入最小生成树的话， 会形成回路。 这就是判断回路的方式。那么判别是否构成回路的方法就是：如果在加入之前的边的两个顶点的终点是同一个点，则说明出现了回路。

3.3 代码实现

package algorithm.kruskal;import java.util.Arrays;public  class KruskalAlgorithm {private Edata[] edges; // 图中的边private int edgeNum;//边的个数private char[] vertexes;//顶点数组private int[][] matrix;//邻接矩阵private static final int INF = Integer.MAX_VALUE;// 使用INF表示两个顶点不能连通public static void main(String[] args) {char[] vertexes = {'A','B','C','D','E','F','G'};int[][] matrix = {//0表示自己和自己连接，有具体的权值就是能连通，INF表示不能连通/*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}};KruskalAlgorithm kruskalAlgorithm = new KruskalAlgorithm(vertexes, matrix);kruskalAlgorithm.print();kruskalAlgorithm.kruskal();}public  KruskalAlgorithm(char[] vertexes, int[][] matrix){//初始化顶点数和边的个数int vlen = vertexes.length;//初始化顶点，复制拷贝的方式this.vertexes = new char[vlen];for (int i = 0;i < vertexes.length;i++){this.vertexes[i] = vertexes[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++;}}}//获取图中的边，放到Edata数组中，通过邻接矩阵来获取int index = 0;edges = new Edata[edgeNum];for(int i = 0;i < vertexes.length;i++){for(int j = i + 1;j < vertexes.length;j++){if(this.matrix[i][j] != INF){edges[index++] = new Edata(vertexes[i], vertexes[j], matrix[i][j]);}}}}//生成最小生成树public void kruskal(){int index = 0;//表示最后结果数组的索引int[] end = new int[edgeNum];//用于保存已有生成树的顶点的终点//创建结果Edata[] res = new Edata[edgeNum];//获取图中所有的边的集合,一共有12条边System.out.println("获取图的边的集合" + Arrays.toString(edges) + "共" + edges.length + "条边");//按照边的权值大小排序Arrays.sort(edges);for(int i = 0; i < edgeNum;i++){//获取到第i条边的第一个起点和终点int p1 = getPosition(edges[i].start);int p2 = getPosition(edges[i].end);//获取p1/p2这个顶点在已有最小生成树中的终点int m = getEnd(end,p1);int n = getEnd(end,p2) ;//是否构成回路if(m != n){end[m] = n;//设置m在已有最小生成树的终点res[index++] = edges[i];//有一条边加入到res数组中}}System.out.println("最小生成树为=");for(int i = 0;i < index;i++){System.out.println(res[i]);}}//打印邻接矩阵的方法public void print(){System.out.println("邻接矩阵为");for (int i = 0;i < vertexes.length;i++){for (int j = 0; j < vertexes.length;j++){System.out.printf("%-12d\t",matrix[i][j]);}System.out.println();}}//获取顶点的下标值private int getPosition(char ch){for(int i = 0;i < vertexes.length;i++){if(vertexes[i] == ch){return i;}}return -1;}/*** @param ends 记录各个顶点对应的终点* @param i 表示传入的顶点对应的下标* @return*///获取下标为i的顶点的终点private int getEnd(int[] ends, int i){while(ends[i] != 0){i = ends[i];}return i;}
}//Edata类，它的对象实例就是一条边
class Edata implements Comparable<Edata>{char start;//边的一个点char end;//边的终点int weight;//边的权值//构造器public Edata(char start, char end, int weight) {this.start = start;this.end = end;this.weight = weight;}@Overridepublic String toString() {return"{<" + start +"," + end +">, weight=" + weight + "}";}@Overridepublic int compareTo(Edata o) {return this.weight - o.weight;}
}

运行结果：
在这里插入图片描述

这篇关于最小生成树和普利姆算法及克鲁斯卡尔算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/558447。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
AI一键生成 PPT

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人，是不是经常需要制作各种PPT来分享我的生活和想法。但是，你们知道，有时候灵感来了，时间却不够用了！😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手！🌟 什么是Kimi？ 一款月之暗面科技有限公司开发的AI办公工具，帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师，Kimi都能够为你的办公文
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
pdfmake生成pdf的使用

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据，将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...
poj 1287 Networking（prim or kruscal最小生成树）

poj 1287 Networking（prim or kruscal最小生成树）

题意给你点与点间距离，求最小生成树。 注意点是，两点之间可能有不同的路，输入的时候选择最小的，和之前有道最短路WA的题目类似。 prim代码： #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2