最小生成树算法
算法 生成 最小
2023-09-27 14:26:28 时间
简介:最小生成树算法一共有两种,分别是kruskal算法和prim算法。也属于贪心算法,它的目的就是给定无向图、权值以及顶点,求联通所有边的权值和最小。
kruskal算法:
先构造一个只含 n 个顶点、而边集为空的子图,把子图中各个顶点看成各棵树上的根结点,之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,即把两棵树合成一棵树,反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直到森林中只有一棵树,也即子图中含有 n-1 条边为止。
这个算法实现就是先利用快排把从小到大排序,贪心算法取最优边,然后利用并查集判断两边是否已经在一个集合中。
核心代码:
for(i=1;i<=m;i++)//开始从小到大枚举每一条边
{
if(merge(e[i].u,e[i].v))//利用并查集判断两个边是否已经在一个集合中
{
count++;
sum=sum+e[i].w;
}
if(count==n-1)//到n-1条边后退出循环
break;
}
prim算法:
算法流程:
1、从任意一个顶点构造生成树,然后用book[]数组记录标记的点。
2、用dis[]数组记录生成树到各个顶点的距离
3、从dis[]数组中选出离生成树最近的顶点加入生成树中,如果dis[k]>e[j][k],则重新更新dis[k]。
4、重复第三步,直到count==n.
核心代码:
book[1]=1;//将1号顶点加入生成树
count++;
while(count<n)
{
min=inf;
for(i=1;i<=n;i++)
{
if(book[i]==0&&dis[i]<min)
{
min=dis[i];
j=i;
}
}
book[j]=1;
count++;
sum+=dis[j];
for(k=1;k<=n;k++)//扫描当前j所在的顶点,再以j为中间点,更新生成树到每一个非树顶点的位置
{
if(book[k]==0&&dis[k]>e[j][k])
dis[k]=e[j][k];
}
}
相关文章
- C++常用算法(五):生成【accumulate:计算容器元素累计总和】【fill:向容器中添加元素】
- 图算法(七):带一般过滤条件最短路径(Filtered Shortest Path)【适用场景:用于路径设计、网络规划等,通过对点边条件的过滤,控制最短路径的生成】【寻找两点间满足过滤条件的最短路径】
- 【风光场景生成】基于改进ISODATA的负荷曲线聚类算法(Matlab代码实现)
- 计及需求响应的粒子群算法求解风能、光伏、柴油机、储能容量优化配置(Matlab代码实现)
- AVX图像算法优化系列一: 初步接触AVX。
- 利用tween.js算法生成缓动效果
- [算法经典] 约瑟夫环问题
- 机器学习算法中随机数的生成
- LeetCode_递归_回溯算法_中等_22.括号生成
- php抽奖概率算法(刮刮卡,大转盘)
- 贪心算法(Greedy Algorithm)之最小生成树 克鲁斯卡尔算法(Kruskal's algorithm)
- Java实现Prim最小生成树算法
- 数据结构与算法之最好学的最小生成树
- 858. Prim算法求最小生成树
- Prim算法、Kruskal算法和最小生成树 | Minimum Spanning Tree
- 遗传编程(GA,genetic programming)算法初探,以及用遗传编程自动生成符合题解的正则表达式的实践
- AcWing 858. Prim算法求最小生成树
- 一个UUID生成算法的C语言实现——WIN32版本
- 一个UUID生成算法的C语言实现 --- WIN32版本 .
- Linux-3.14.12内存管理笔记【伙伴管理算法(1)】
- 一个UUID生成算法的C语言实现 --- WIN32版本 .