【算法】prim算法(最小生成树)(与Dijkstra算法的比较)
最小生成树:
生成树的定义:给定一个无向图,如果它的某个子图中任意两个顶点都互相连通并且是一棵树,那么这棵树就叫做生成树。(Spanning Tree)
最小生成树的定义:在生成树的基础上,如果边上有权值,那么使得边权和最小的生成树叫做最小生成树。(Minimum Spanning Tree )
解决生成树有两种常用的算法:Kruskal算法和prim算法。
这里我们讲的是prim算法求生成树的解法。
算法思想:
ans = 0;(表示权值和)
1.在无向图的基础上,想象我们有一个点的集合X(初始状态为空)。
2.在集合X中加入一个初始点x,用这个初始点更新其他点离集合X的距离mincost[ ],标记初始点为使用过(使用过:加入集合X)。
3.找一个未使用过(集合X外的点)的离集合X最小距离最小的点,找到了这样一个点,将这个点加入集合X,ans += 这个与集合X的距离,
用这个新加入的点更新其他点离集合X的最小距离mincost[ ],标记新加入的点为使用过,继续执行第3步;找不到这样一个点,则进入第4步。
4.输出ans。
mincost[i] 表示点i离集合X的最小距离。(离集合X中所有点中最近的点的距离)
简单来说就是:
想象一下,有10张面额不同的毛爷爷在你面前,每次只能拿1张,只能拿5次,你肯定会每次都拿这n张(n<=10)中最大的那张,
这样拿5次,让总额最大。这个算法也是同样的道理,不断的加入可触及的最近的点,最后权值一定是最小的。
额,当然10张不同的毛爷爷是不存在的。所以一分都拿不到,还是看代码吧:
代码:
#include <bits\stdc++.h>
using namespace std;
#define INF 2147483647
#define MAX_V 1000
#define MAX_E 2000 int cost[MAX_V][MAX_V]; // cost[i][j] 表示顶点i到顶点j的权值,不存在时为INF
int mincost[MAX_V]; // mincost[i] 表示i点与集合X的最小距离
bool used[MAX_V]; // used[i]表示点i是否在集合中
int V; //顶点数 //表示从点x产生的最小生成树,这么考虑是因为整个图可能不连通
int prim(int x){
//最初X集合为空,每个点到集合X的最小距离都是INF
for(int i = ;i < V; ++i){
mincost[i] = INF;
used[i] = false;
} //将点x与集合X的距离置为0,第一次集合X会加入点x
mincost[x] = ; int res = ; while(true){
int v = -;
//找到离集合X最近的点,第一次加入点x
for(int u = ;u < V; ++u){
if(!used[u] && (v == - || mincost[u] < mincost[v])) v = u;
}
//如果所有点可达的点都加入集合X中了,就跳出
if(v == -) break;
used[v] = true;
res += mincost[v]; mincost[v] = ; //把点v加入到集合X中,这一步帮助理解,可写可不写 ,因为cost[v][v] = 0 //用新加入的点v更新其他点离与集合X的最小距离
for(int u = ;u < V; ++u){
mincost[u] = min(mincost[u] , cost[v][u]);
}
}
return res;
} int main(){
}
与Dijkstra算法的比较
Prim算法与Dijkstra算法都是从某个点出发,不断加入最近的点。最终都要把所有可以加的点加完。
Prim算法是求最小生成树,Dijkstra是求单源最短路径。
来个Dijkstra求单源最短路径的代码,与Prim算法比较一下:
#include <bits\stdc++.h>
using namespace std;
#define INF 2147483647
#define MAX_V 1000
#define MAX_E 2000 //单源最短路径问题(Dijkstra算法) int cost[MAX_V][MAX_V]; //cost[u][v]表示e = (u,v)的权值
int d[MAX_V]; //顶点s出发的最短距离 //不同处1
bool used[MAX_V]; //标记使用过的点
int V; //顶点数 void dijkstra(int s){
fill(d, d+V, INF);
fill(used, used + V, INF);
d[s] = ; while(true){
int v = -; //找到一个距离最近的没有使用过的点
for(int u = ;u < V; u++){
if(!used[u] && (v == - || d[u] < d[v])) v = u;
}
//如果所有的点都被使用过了,则break
if(v == -) break; //标记当前点被使用过了
used[v] = true; //更新这个找到的距离最小的点所连的点的距离
for(int u = ;u < V; u++){
d[u] = min(d[u], d[v] + cost[v][u]); //不同处2
} }
} int main(){
}
我们可以看到代码基本上是一样的,只有
不同处1:Djikstra中用d[i]表示i点离源点的最短距离,Prim中用mincost[i] 表示i点与集合X的距离。
不同处2:Djikstra中更新d[u] = min( d[u] , d[v] + cost[v][u] ); 用新加入的点更新其他点与源点的最小距离。
Prim中更新mincost[u] = min( mincost[u] , cost[v][u] ); 用新加入的点更新点i与集合X的最小距离。
我认为只用加几行代码,无论是在prim中加,还是在Dijkstra中加,就既可以求单源最短路径,又可以求最小生成树了。
最新文章
- window下使用Redis Cluster部署Redis集群
- IRIS数据集的分析-数据挖掘和python入门-零门槛
- LeetCode ";Third Maximum Number";
- 5ucms后台调用标签
- asp.net mvc 使用ajax请求 控制器 (PartialViewResult)分部的action,得到一个分部视图(PartialView)的HTML,进行渲染
- mysql破解root用户密码总结
- 删除表空间时,遇到了ORA-14404错误
- Apache OFBiz 学习笔记 之 服务引擎 二
- wordpress 如何从后台数据库修改theme(图文教程)
- 【HDOJ】2589 正方形划分
- Premature optimization is the root of all evil.
- phpstorm 同步远程服务器代码
- 用Nifi 从web api 取数据到HDFS
- ExtJS4中设置tabpanel的tab高度问题
- Linux Mint Mate 常用
- logstash 解析日志文件
- mac nginx 安装教程
- nginx中location详解
- Git学习-->GitLab如何修改时区?
- 如何导入数据到Mysql