最近在学习算法,在学习最小生成树的过程中,感觉算法思想很简单,但实现起来对于我这样的菜鸟来说有些困难,后来上网搜了一些文章,发现这篇讲得很清楚,与大家分享一下
http://blog.csdn.net/fengchaokobe/article/details/7521780。我着重研究了一下克鲁斯卡尔算法。
克鲁斯卡尔算法
克鲁斯卡尔算法的思想如下:
克鲁斯卡尔算法的核心思想是:在带权连通图中,不断地在边集合中找到最小的边,如果该边满足得到最小生成树的条件,就将其构造,直到最后得到一颗最小生成树。
克鲁斯卡尔算法的执行步骤:
第一步:在带权连通图中,将边的权值排序;
第二步:判断是否需要选择这条边(此时图中的边已按权值从小到大排好序)。判断的依据是边的两个顶点是否已连通,如果连通则继续下一条;如果不连通,那么就选择使其连通。
第三步:循环第二步,直到图中所有的顶点都在同一个连通分量中,即得到最小生成树。
在一条新边加入时,要判断是否形成环路(其实前两条边不用判断,大家明白的哈),那么该如何判断呢?
1.如果没有形成回路,那么直接将其连通。此时,对于边的集合又要做一次判断:这两个点是否在已找到点的集合中出现过?
①.如果两个点都没有出现过,那么将这两个点都加入已找到点的集合中;
②.如果其中一个点在集合中出现过,那么将另一个没有出现过的点加入到集合中;
③.如果这两个点都出现过,则不用加入到集合中。
2.如果形成回路,不符合要求,直接进行下一次操作。
通过生成的过程可以看出,能否得到最小生成树的核心问题就是上面所描述的判断法则。那么,我们如何用算法来描述判断法则呢?我认为只需要三个步骤即可:
⒈将某次操作选择的边XY的两个顶点X和Y和已找到点的集合作比较,如果
①.这两个点都在已找到点的集合中,那么return 2;
②.这两个点有一个在已找到点的集合中,那么return 1;
③这两个点都不在一找到点的集合中,那么return 0;
⒉当返回值为0或1时,可判定不会形成回路;
⒊当返回值为2时,判定能形成回路的依据是:假如能形成回路,设能形成回路的点的集合中有A,B,C,D四个点,那么以点A为起始点,绕环路一周后必能回到点A。如果能回到,则形成回路;如果不能,则不能形成回路。
具体的流程在我给出的链接中英讲得很好了,在这里我就不赘述了。
在判断是否出现环路时,我采用了如下方法:
转自http://blog.csdn.net/lyflower/archive/2008/03/01/2137710.aspx。
如果存在回路,则必存在一个子图,是一个环路。环路中所有顶点的度>=2。
n算法:
第一步:删除所有度<=1的顶点及相关的边,并将另外与这些边相关的其它顶点的度减一。
第二步:将度数变为1的顶点排入队列,并从该队列中取出一个顶点重复步骤一。
如果最后还有未删除顶点,则存在环,否则没有环。
n算法分析:
由于有m条边,n个顶点。如果m>=n,则根据图论知识可直接判断存在环路。
(证明:如果没有环路,则该图必然是k棵树 k>=1。根据树的性质,边的数目m = n-k。k>=1,所以:m<n)
如果m<n 则按照上面的算法每删除一个度为0的顶点操作一次(最多n次),或每删除一个度为1的顶点(同时删一条边)操作一次(最多m次)。这两种操作的总数不会超过m+n。由于m<n,所以算法复杂度为O(n)
(这种判断环路的方法很简单吧)
下面我贴出我的代码,希望大牛们不要喷我,我只是实现了找出最小生成树的功能,具体效率方面没有考虑(ps:只针对于无向图)
import java.util.Scanner;
//存储边,及边的结点
class dataType{
int value;
String startNode;
String endNode;
}
//存储结点,flag用于标记结点是否已经加入到最小生成树中
class dataType1{
String node;
int flag;
}
public class KruskalAlgorithm {
//对边进行排序
static void sort(dataType[] arr,int n)
{
int temp;
String temp1;
for(int i=0;i<n;i++)
{
int flag=0;
for(int j = 0;j<n-i-1;j++)
{
if(arr[j].value>arr[j+1].value)
{
temp = arr[j].value;
arr[j].value = arr[j+1].value;
arr[j+1].value = temp;
temp1=arr[j].startNode;
arr[j].startNode=arr[j+1].startNode;
arr[j+1].startNode=temp1;
temp1=arr[j].endNode;
arr[j].endNode=arr[j+1].endNode;
arr[j+1].endNode=temp1;
flag++;
}
}
if(flag==0)
break;
}
}
//判断能否出现回路
static int isLoop(dataType1 arr1[],int num, int edgeNum)
{
int nodeFlag=0;
for(int i=0;i<num;i++)
{
if(arr1[i].flag==1)
{
nodeFlag++;
}
}
if(nodeFlag>(edgeNum+1))
return 0;
else
return 1;
}
//判断选择的一条边中有几个顶点已经出现过
static int isEmerge(String startNode,String endNode,dataType1[] arr1,int num)
{
int loop = 0;
for(int i = 0;i<num;i++)
{
if(arr1[i].node.compareTo(startNode)==0)
{
if(arr1[i].flag==1)
{
loop++;
}
else
{
arr1[i].flag=1;
}
}
if(arr1[i].node.compareTo(endNode)==0)
{
if(arr1[i].flag==1)
{
loop++;
}
else
{
arr1[i].flag=1;
}
}
}
/*for(int i=0;i<num;i++)
{
System.out.print("("+arr1[i].node+","+arr1[i].flag+") ");
}
System.out.println();*/
return loop;
}
public static void main(String[] args) {
int sum=0;
int edgeNum = 0;
System.out.print("请输入图中边的条数:");
Scanner input = new Scanner(System.in);
int n = input.nextInt();
System.out.print("请输入图中点的个数:");
int num = input.nextInt();
dataType1[] arr1 = new dataType1[num];
System.out.print("请输入图中的点:");
for(int j = 0;j<num;j++)
{
arr1[j] = new dataType1();
arr1[j].node=input.next();
arr1[j].flag = 0;
}
int i=0;
int j;
dataType[] arr = new dataType[n];
while(true)
{
if(i<n)
{
System.out.print("请输入边的长度,以及边的两个顶点");
arr[i] = new dataType();
j = input.nextInt();
if(j==0)
{
break;
}else
{
arr[i].value = j;
arr[i].startNode = input.next();
arr[i].endNode = input.next();
i++;
}
}
else
{
break;
}
}
System.out.println("开始对边进行排序:");
sort(arr,n);
System.out.println("完成排序:");
for(i = 0;i<n;i++)
{
System.out.print("("+arr[i].value+","+arr[i].startNode+","+arr[i].endNode+") ");
}
System.out.println();
for(int k =0;k<n;k++)
{
if(edgeNum<num)
{
if(k<2)//加入的第一条边、第二条边不用判断是否形成环路
{
int loop = isEmerge(arr[k].startNode,arr[k].endNode,arr1,num);//将边的结点加入到已选集合
sum=sum+arr[k].value;
edgeNum++;
System.out.print("("+arr[k].startNode+","+arr[k].endNode+") ");
}else{
int loop = isEmerge(arr[k].startNode,arr[k].endNode,arr1,num);
if(loop==0)
{
sum = sum+arr[k].value;
edgeNum++;
System.out.print("("+arr[k].startNode+","+arr[k].endNode+") ");
}
if(loop==1)
{
sum = sum+arr[k].value;
edgeNum++;
System.out.print("("+arr[k].startNode+","+arr[k].endNode+") ");
}
if(loop==2)
{
if(isLoop(arr1,num,edgeNum)==0)
{
sum = sum+arr[k].value;
edgeNum++;
System.out.print("("+arr[k].startNode+","+arr[k].endNode+") ");
}
}
}
}else
{
break;
}
}
System.out.print("最小生成树的长度为:"+sum);
}
}
分享到:
相关推荐
人力资源+大数据+薪酬报告+涨薪调薪,在学习、工作生活中,越来越多的事务都会使用到报告,通常情况下,报告的内容含量大、篇幅较长。那么什么样的薪酬报告才是有效的呢?以下是小编精心整理的调薪申请报告,欢迎大家分享。相信老板看到这样的报告,一定会考虑涨薪的哦。
迅雷
内容概要:本文介绍了一个基于Java的简单命令行学生管理系统。该项目包含了添加、查看、更新和删除学生的全部功能,并对每个部分的实现进行了详尽展示,包括关键源代码以及操作步骤指引。项目的主干由多个重要文件构成:Student.java 负责定义学生类及其属性访问器方法;StudentManager.java 实现对学生信息的操作处理逻辑,如创建、读取、更新、销毁(CRUD)等;而 Main.java 则用于执行主程序逻辑并初始化StudentManager实例,提供命令行交互环境以供用户执行相应操作。
one-api本地部署ollama+deepseek-r1
krpanodew,全景编辑器。一键生成全景图和连续前景图并生成场景。
基于Matlab 2021的两电平拓扑三相桥式逆变并网仿真:双环PI控制、SPWM调制与LCL滤波研究,基于Matlab2021的电压型三相桥式逆变并网仿真研究:双环PI控制、SPWM调制与LCL滤波器的应用,电压型三相桥式逆变并网仿真Matlab2021 电路采用两电平拓扑,采用双环PI控制, 变部分加设PLL锁相环, 采用SPWM调制,逆变器输出端加设LCL滤波器,并入电网。 可以得到逆变器输出端为三电平的线电压波形,滤波后可以得到对称三相电压、电流波形。 无需发,联系即可发邮件。 ,三相桥式逆变器;两电平拓扑;双环PI控制;电压型逆变;PLL锁相环;SPWM调制;LCL滤波器;电网并网;线电压波形。,Matlab 2021三相桥式逆变并网仿真:双环PI控制与LCL滤波器应用
纯电动汽车零部件建模机理与前后向仿真控制策略详解:聚焦BMS、再生制动及电机驱动扭矩策略,纯电动汽车零部件建模机理与前后向仿真控制策略详解:从Cruise到ADVISOR建模实践与能量流解析,纯电动汽车各零部件建模机理及BMS、再生制动和电机驱动扭矩策略,逻辑清晰公式明晰。 主要从前向和后向仿真两大类分别阐述建模机理和控制策略。 前向模型主要参考Cruise建模及相关文献,后向模型主要参考ADVISOR建模且对其自带的纯电动汽车模型进行注释分析。 现打包,包含文档、参考模型和参考文献等,适合学习纯电动汽车建模机理,整篇文档主要为公式和整车能量流走向 ,关键零部件建模; BMS; 再生制动; 电机驱动扭矩策略; 前向仿真建模; 后向仿真建模; 能量流走向; 公式明晰; 文档参考。,纯电动整车建模与控制策略解析:BMS、再生制动与电机驱动扭矩的深度研究
情人节html+css源码
基于Yolo系列算法的计算机视觉与人工智能目标检测技术研究,基于Yolo系列算法的计算机视觉与人工智能目标检测技术分析,基于yolo系列的目标检测分析,人工智能,计算机视觉。 ,基于yolo系列;目标检测分析;人工智能;计算机视觉,基于Yolo系列的人工智能计算机视觉目标检测分析
项目工程资源经过严格测试运行并且功能上ok,可实现复现复刻,拿到资料包后可实现复现出一样的项目,本人系统开发经验充足(全栈全领域),有任何使用问题欢迎随时与我联系,我会抽时间努力为您解惑,提供帮助 【资源内容】:包含源码+工程文件+说明等。答辩评审平均分达到96分,放心下载使用!可实现复现;设计报告也可借鉴此项目;该资源内项目代码都经过测试运行,功能ok 【项目价值】:可用在相关项目设计中,皆可应用在项目、毕业设计、课程设计、期末/期中/大作业、工程实训、大创等学科竞赛比赛、初期项目立项、学习/练手等方面,可借鉴此优质项目实现复刻,设计报告也可借鉴此项目,也可基于此项目来扩展开发出更多功能 【提供帮助】:有任何使用上的问题欢迎随时与我联系,抽时间努力解答解惑,提供帮助 【附带帮助】:若还需要相关开发工具、学习资料等,我会提供帮助,提供资料,鼓励学习进步 下载后请首先打开说明文件(如有);整理时不同项目所包含资源内容不同;项目工程可实现复现复刻,如果基础还行,也可在此程序基础上进行修改,以实现其它功能。供开源学习/技术交流/学习参考,勿用于商业用途。质量优质,放心下载使用,资源为网络商品(电子资料类)基于网络商品和电子资料商品的性质和特征不支持退款,质量优质,放心下载使用
Epson_L130,需要删除后缀
双重搜索算法BAS-SCA融合正余弦算法优化极限学习机ELM:混合改进机制,避免局部最优,提高收敛精度,双重搜索算法BAS-SCA与正余弦算法融合优化极限学习机ELM:避免局部最优的混合改进机制,提高收敛精度,融合天牛须算法与正余弦算法的双重搜索算法BAS-SCA优化极限学习机ELM,采用混合改进机制可有效避免搜索陷入局部最优,收敛精度高 ,关键词:融合算法;双重搜索;BAS-SCA;优化;极限学习机ELM;混合改进机制;局部最优;收敛精度高。,双算法融合优化ELM,高效避免局部最优,提高收敛精度
基于NPC五电平逆变器的并网逆变器PQ控制技术研究——通过功率闭环控制实现精确电网相位锁相环与高效并网功率因数调整,基于双二阶广义积分器的NPC五电平逆变器并网PQ控制技术:功率闭环控制与离散化仿真实现,NPC五电平逆变器。 并网逆变器PQ控制。 通过功率闭环控制,实现并网单位功率因数,即并网电流与网侧电压同相位。 为了得到电网电网相位,采用基于双二阶广义积分器的锁相环,该锁相环可以快速准确无误的得到电网相位。 且在初始阶段,就可以得到电网相位,比Matlab自带的锁相环要快很多。 并网有功设定为50kW,无功设定为0,通过仿真可以看出,很快实现了给定的并网功率。 整个仿真全部离散化,包括采样与控制的离散,控制与采样环节没有使用simulink自带的模块搭建,全部手工搭建。 ,基于上述信息,以下是几个核心关键词: NPC五电平逆变器; 并网逆变器PQ控制; 功率闭环控制; 电网相位; 快速准确锁相环; 离散化仿真; 手工搭建。,离散化控制的五电平逆变器并网策略研究
双闭环控制的Buck变换器:实现软启动与离散化仿真的完美电压跟随,Buck变换器:双闭环控制与软启动策略,输出电压平稳跟随参考电压,buck变器。 采用双闭环控制,外环为电压环,内环为电流环。 其中,内环采用平均电流采样。 buck变器采用软启动控制,可以使电流不突变。 从仿真图中可以看出,在0.5秒的时间内,完成了软启动,输出电压完美跟随参考电压。 在1秒时,启动加载。 此时,输出电压有微小的变动,但是马上跟随给定参考电压。 整个仿真完全离散化,主电路与控制部分以不同的步长运行,更加贴合实际。 ,buck变换器;双闭环控制;外环电压环;内环电流环;平均电流采样;软启动控制;离散化仿真;主电路;控制部分步长,双闭环控制的Buck变换器:软启动与精确电压跟随的仿真研究
大宗商品价格指数(Commodity Consumer Price Index,简称CCPI)是一个滞后指标,也是通货膨胀的早期预警指标,能反映通货膨胀的程度。它是特定商品按价格加权计算的指数,反映在不同时点上的价格变动情况。 大宗商品价格指数是一个重要的经济指标,能够反映大宗商品市场的整体价格水平和变动趋势,对于经济预测、政策制定和投资决策等方面都具有重要意义。 数据名称:大宗商品价格指数(CCPI) 数据年份:2010-2024年 ## *02、相关数据* 时间、大宗商品价格指数(CCPI):总指数。
版本号:2.5.6 – 多开版 更新内容: 1.修复核销记录入口显示 2.修复核销记录中店铺显示 3.修改核销记录中的状态显示 4.修复附近商品订单问题 无需更新小程序 版本号:2.5.5 – 多开版 更新内容: 1.修复指定中奖的问题 2.优化提现功能 3.修改商品销售统计 4.修改后台统计页面 5.小程序新增核销记录 6.修复商家抽佣不到账的问题 7.修复机器人参团跟指定中奖数量叠加的问题 需要更新小程序