常用的十大算法-普利姆算法

2024-01-04 00:40
文章标签 算法 常用 十大 普利

本文主要是介绍常用的十大算法-普利姆算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

普利姆算法

介绍

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

普利姆算法步骤

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

普利姆算法实践(修路问题)

有7个村庄(A,B,C,D,E,F,G),现在需要把7个村庄连通,各个村庄的距离用边线表示权,如何修路保证各个村庄都能连通,并且总的修建公路里程最短。

在这里插入图片描述

package algorithm;/*** @author taoke* @desc 普利姆算法(修路问题)* @email 1504806660@qq.com* @date 2022/1/25*/
public class Prim {//最大值private static final int N = 65535;//顶点private static final char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};//临界矩阵,N表示不通private static final int[][] matrix = {{0, 5, 7, N, N, N, 2},{5, 0, N, 9, N, N, 3},{7, N, 0, N, 8, N, N},{N, 9, N, 0, N, 4, N},{N, N, 8, N, 0, 5, 4},{N, N, N, 4, 5, 0, 6},{2, 3, N, N, 4, 6, 0}};/*** 普利姆算法** @param v 从第几个顶点开始*/public static void prim(int v) {//所有顶点是否被访问过boolean[] visited = new boolean[vertex.length];//把当前这个顶点标记为已访问visited[v] = true;//h1,h2表示两个顶点int h1 = -1;int h2 = -1;//初始值int minWeight = N;//顶点数量为vertex个,普利姆算法生成vertex-1条边for (int k = 1; k < vertex.length; k++) {//确定每次生成的子图和哪个顶点的距离最近for (int i = 0; i < vertex.length; i++) {for (int j = 0; j < vertex.length; j++) {if (visited[i] && !visited[j] && matrix[i][j] < minWeight) {//替换minWeight(寻找已访问过的节点和未访问过的节点,权值最小的边)minWeight = matrix[i][j];h1 = i;h2 = j;}}}//找到一条最小的边System.out.println("边<" + vertex[h1] + "," + vertex[h2] + ">权值:" + minWeight);//标记顶点为已访问visited[h2] = true;//重新设置为最大值minWeight = N;}}public static void main(String[] args) {prim(0);}
}

计算结果

在这里插入图片描述

这篇关于常用的十大算法-普利姆算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/567597

相关文章

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

VUE动态绑定class类的三种常用方式及适用场景详解

《VUE动态绑定class类的三种常用方式及适用场景详解》文章介绍了在实际开发中动态绑定class的三种常见情况及其解决方案,包括根据不同的返回值渲染不同的class样式、给模块添加基础样式以及根据设... 目录前言1.动态选择class样式(对象添加:情景一)2.动态添加一个class样式(字符串添加:情

Java 枚举的常用技巧汇总

《Java枚举的常用技巧汇总》在Java中,枚举类型是一种特殊的数据类型,允许定义一组固定的常量,默认情况下,toString方法返回枚举常量的名称,本文提供了一个完整的代码示例,展示了如何在Jav... 目录一、枚举的基本概念1. 什么是枚举?2. 基本枚举示例3. 枚举的优势二、枚举的高级用法1. 枚举

IDEA常用插件之代码扫描SonarLint详解

《IDEA常用插件之代码扫描SonarLint详解》SonarLint是一款用于代码扫描的插件,可以帮助查找隐藏的bug,下载并安装插件后,右键点击项目并选择“Analyze”、“Analyzewit... 目录SonajavascriptrLint 查找隐藏的bug下载安装插件扫描代码查看结果总结Sona

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

JS常用组件收集

收集了一些平时遇到的前端比较优秀的组件,方便以后开发的时候查找!!! 函数工具: Lodash 页面固定: stickUp、jQuery.Pin 轮播: unslider、swiper 开关: switch 复选框: icheck 气泡: grumble 隐藏元素: Headroom

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

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

康拓展开(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]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

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

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个