普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点,且其所有边的权值之和亦为最小。
以下是数据结构中关于普里姆算法的操作(编程风格参考严蔚敏版数据结构)。
头文件及宏
#include<iostream>
#include<stdio.h>
using namespace std;
typedef char VerTexType;
typedef int ArcType;
#define MaxInt 32767
#define MVNum 100
#define OK 1
#define ERROR -1;
typedef int status;
图以及最短边集合的声明
typedef struct{
VerTexType vexs[MVNum] {'A','B','C','D','E','F'};
ArcType arcs[MVNum][MVNum];
int vexnum = 6,arcnum = 10;
}AMGraph;
typedef struct{
VerTexType adjvex;//最小边在顶点集U的顶点
ArcType lowcost;//最小边上的权值
}Closedge[MVNum];
特别说明!!!!!
在Closedge中,起点是通过节点VerTexType类型变量表示,而终点是通过下标int类型变量来表示。
adjvex就是某条边的起点,lowcost就是两点之间权值(距离),closedge[i]里的i是终点的下标。
理解好这个很重要,如果这个理解不好,那就不知道Prim里close辅助数组是怎么用的了。
举个例子
如何算出上图里的最小生成树呢?
老样子先弄出邻接矩阵:
Prim核心算法:
void Prim(AMGraph &G,VerTexType v){
int vi = LocateVex(G,v);//获取起始点的下标
Closedge close;//辅助数组,用来记录不同点之间的距离以及起始位置(可理解为是一个点边集合)
for(int i=0;i<G.vexnum;i++){
if(vi!=i){
close[i].adjvex=v;
close[i].lowcost=G.arcs[vi][i];//初始化辅助数组close,让起点直连其它节点(就是假设起点到全部点的距离都是最短)
}else{
close[i].lowcost = 0;
}
}
for(int i=1;i<G.vexnum;i++){//i从1开始是因为循环不需要执行vexnum次,不必管节点到自己的距离
int k = Min(close,G);//获取当前点边集合里边权值最小的终点(close里下标表示终点,adjvex表示起点,lowcost表示权值)
VerTexType start = close[k].adjvex;//当前边集合里最短边的起点
VerTexType end = G.vexs[k];//当前边集合里最短边的终点
cout<<start<<"-"<<close[k].lowcost<<"-"<<end<<endl;//输出本次找出来的最短边及端点
for(int j=0;j<G.vexnum;j++){//更新close表
if(G.arcs[k][j]<close[j].lowcost){//如果end到j点的距离小于start到j点的距离
//这是以对象的形式简写
close[j] = {G.vexs[k],G.arcs[k][j]};//最短距离从start到j点距离修改成end到j点的距离
//等价于这样写
// close[i].adjvex=G.vexs[k];
// close[i].lowcost=G.arcs[k][j];
}//if
}//for
}
}
算法执行过程(红色线表示更新的边,蓝色的表示已被选取的边,黑色的表示当前步骤未被操作的边):
初始化辅助数组close。这一步目的是让起点直连其它的节点(就是说假设起点到其它全部节点的距离是最短的)。画出来是这样的:
此时的close记录的就是从A到其它全部节点的距离的集合。
开始第一轮循环:在close这些边里选出最短的边,AC的值最小,记录起点为A终点为C(不必做更新操作,因为这条边本就在close里)。然后以AC同时和BEFD比较距离(权值大小)。比如:A到B的距离为为6,C到B的距离是5,close里本来是A到B的边变成C到B,然后close变成如下情况:
然后AC和E比较,和F比较、和D比较,CE<AE,CF<AF。得出来的close就是这样:
第二轮循环开始:然后选出最短的那条:CF(权值为4)。此时close是这个情况:
然后A、C、F同时比较距离和B、E、D的距离。CB权值最小close不变,C和F到E距离一致,保持CE相连,FD权值比CD和AD都小,连接FD,更新close。此时的close是这样子的:
第三轮循环开始:此时的close是这样的:
A、C、F、D同时和B、E比较距离:发现是CB最短(但是在2轮循环里CB这条边已经在close里了,就没有实际更新close的操作)
第四轮循环开始:此时的close是这样的:
A、B、C、D、F同时与E比较权值:BE的距离比原先的CE短,取消CE更新为BE。此时的close是这个情况:
此时最小生成树生成完毕。最后结果如下所示:
代码执行结果:
源码
#include<iostream>
#include<stdio.h>
using namespace std;
typedef char VerTexType;
typedef int ArcType;
#define MaxInt 32767
#define MVNum 100
#define OK 1
#define ERROR -1;
typedef int status;
typedef struct{
VerTexType vexs[MVNum] {'A','B','C','D','E','F'};
ArcType arcs[MVNum][MVNum];
int vexnum = 6,arcnum = 10;
}AMGraph;
typedef struct{
VerTexType adjvex;//最小边在顶点集U的顶点
ArcType lowcost;//最小边上的权值
}Closedge[MVNum];
//其实说白了就是adjvex就是某条边的起点,lowcost就是权值(距离),closedge[i]的i是终点。
//理解好这个很重要。
status CreateUDN(AMGraph &G){//创建无向图
for(int i=0;i<G.vexnum;i++){
for(int j=0;j<G.vexnum;j++){
if(i==j){
G.arcs[i][j] = 0;
}else
G.arcs[i][j] = MaxInt;//初始状态全部节点之间相互不可达
}
}
G.arcs[0][1]=6;G.arcs[0][2]=1;G.arcs[0][3]=5;
G.arcs[1][2]=5;G.arcs[1][4]=3;
G.arcs[2][3]=5;G.arcs[2][4]=6;G.arcs[2][5]=4;
G.arcs[3][5]=2;
G.arcs[4][5]=6;
for(int i=0;i<G.vexnum;i++){
for(int j=0;j<G.vexnum;j++){
if(G.arcs[i][j]!=MaxInt){
G.arcs[j][i] = G.arcs[i][j];
}
}
}//矩阵对称
return OK;
}
void ShowGraph(AMGraph G){
cout<<" ";
for(int i=0;i<G.vexnum;i++){
cout<<" "<<G.vexs[i];
}
cout<<endl;
for(int i=0;i<G.vexnum;i++){
cout<<G.vexs[i]<<" ";
for(int j=0;j<G.vexnum;j++){
if(G.arcs[i][j]==MaxInt){
cout<<"* ";
}else{
cout<<G.arcs[i][j]<<" ";
}
}
cout<<endl;
}
}
int LocateVex(AMGraph G, VerTexType v){
int i;
for(i=0;i<G.vexnum;i++){
if(G.vexs[i]==v){
return i;
}
}
return ERROR;
}
int Min(Closedge close,AMGraph G){
int min = MaxInt;
int mini;
for(int i=0;i<G.vexnum;i++){
if(min>close[i].lowcost&&close[i].lowcost!=0){//不等于0是指不和自身比较,没意义
min = close[i].lowcost;
mini = i;
}
}
// cout<<mini<<endl;
return mini;
}
void Prim(AMGraph &G,VerTexType v){
int vi = LocateVex(G,v);//获取起始点的下标
Closedge close;//辅助数组,用来记录不同点之间的距离以及起始位置(可理解为是一个点边集合)
for(int i=0;i<G.vexnum;i++){
if(vi!=i){
close[i].adjvex=v;
close[i].lowcost=G.arcs[vi][i];//初始化辅助数组close,让起点直连其它节点(就是假设起点到全部点的距离都是最短)
}else{
close[i].lowcost = 0;//0表示自身或该边已被选取。
}
}
for(int i=1;i<G.vexnum;i++){//i从1开始是因为循环不需要执行vexnum次,不必管节点到自己的距离
int k = Min(close,G);//获取当前点边集合里边权值最小的终点(close里下标表示终点,adjvex表示起点,lowcost表示权值)
VerTexType start = close[k].adjvex;//当前边集合里最短边的起点
VerTexType end = G.vexs[k];//当前边集合里最短边的终点
cout<<start<<"-"<<close[k].lowcost<<"-"<<end<<endl;//输出本次找出来的最短边及端点
for(int j=0;j<G.vexnum;j++){//更新close表
if(G.arcs[k][j]<close[j].lowcost){//如果end到j点的距离小于start到j点的距离
//这是以对象的形式简写
close[j] = {G.vexs[k],G.arcs[k][j]};//最短距离从start到j点距离修改成end到j点的距离
//等价于这样写
// close[i].adjvex=G.vexs[k];
// close[i].lowcost=G.arcs[k][j];
}//if
}//for
}
}
int main(){
AMGraph G;
CreateUDN(G);
ShowGraph(G);
Prim(G,'A');
return 0;
}
关于时间复杂度和空间复杂度
设顶点数n,边数e。邻接矩阵:O(n^2) 邻接表:O(elogn)文章来源:https://www.toymoban.com/news/detail-461489.html
敬请批评指正。文章来源地址https://www.toymoban.com/news/detail-461489.html
到了这里,关于数据结构——普里姆(Prim)算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!