prim算法_数据结构 7.4.1 最小生成树 Prim

最小生成树

Minimum Spanning Tree

「最小生成树」这个词包含三部分信息

树生成树最小

什么是树？

树可以看做是一种特殊的图，「树没有回路」有n个顶点的树一定有n-1条边

什么是生成树？

一个连通图的生成树是一个极小连通子图

生成树包含了图中全部n个顶点生成树只有足以构成一棵树的n-1条边

如何得到生成树？

可以通过遍历来得到生成树一个图的生成树不是唯一的，可以有多种形式

❝

有n-1条边不一定是生成树，如上图右下角所示。

❞

生成树的性质

向生成树中任意添加一条边一定构成回路。一个图若存在对应的最小生成树，则此图为连通图，反之也成立。

什么是最小？

对于一个带权图来说，权值之和最小的生成树就是「最小生成树」

最小生成树的实际问题

如图所示，图中一个顶点代表一个村庄，除少数被山川阻隔的路线，村庄之间的距离都以带权边的形式给出，要求你设计一个造价最低的修路方案，把所有的村庄连通。

既然是造价最低，那肯定不是修成像城市那种网状结构。很自然的我们想到了树形结构，当然线性结构算树形结构的一种特殊情况。用计算机来求解，就是图的最小生成树这一类问题。

Prim算法

Prim算法的思路是：从一棵树的根节点开始，让这棵小树慢慢长大。

Prim算法是一种典型的贪心算法

什么是贪？

每一步都要是最好的

什么是好？

对于修路的问题而言，当然是选到权重最小的边

贪心得有度，贪心是有约束条件

约束条件

只能选n-1条边不能形成回路 如果选了这条边就会形成回路，即使这条边的权重最小也不能选下面就来简单模拟一下Prim算法的大致过程

首先从v0开始

选择权重较小的(v0, v1)

选择(v0, v5)

选择(v1, v8)选择(v2, v8)

这里需要注意，选择了(v1, v2)之后会形成环，(v1, v2)不能选择。同理，(v5, v6)也不能选择。选择(v7, v4)选择(v7, v3)，最小生成树建立完成

权重和

下面来看C++ 代码实现

建立邻接矩阵

typedefintVertexType;

typedefshortArcType;

以单字有符号数能取到的最大值32767为∞

输入

9

012345678

010 32767327673276711 327673276732767

100 18 32767327673276716 3276712

3276718 022 327673276732767327678

327673276722 022 3276724 16 21

32767327673276722 026 32767732767

11 32767327673276726 0 17 3276732767

3276716 3276724 3276717 019 32767

327673276732767 16 73276719 032767

3276712 821 327673276732767327670

voidMST_Prim(mgraph*g){

ArcType*lowcost;//存储权值的数组

lowcost=newArcType[g->num_vexs];

lowcost[0]=0;//以v0作为小树的根节点

int*adjvex;

adjvex=newint[g->num_vexs];

adjvex[0]=0;

for(inti=1;inum_vexs;i++){

lowcost[i]=g->arc[0][i];//将那些和v0邻接的边的权值放进数组里(不邻接看成邻接但距离无穷大)

adjvex[i]=0;//初始化这棵树只有v0一个节点

}

intmin;//一定范围内的最小权值

intmin_k;//存储最小权值的顶点下标

constArcTypeInf=32767;//权值的无穷大

for(inti=1;inum_vexs;i++){

min=Inf;

min_k=0;

for(intj=1;jnum_vexs;j++){

//在lowcost里面找到权重最小的边

if(lowcost[j]!=0&&lowcost[j]//lowcost的元素为0则表示该顶点已纳入MST中

min=lowcost[j];

min_k=j;

}

}

cout<''<endl;

lowcost[min_k]=0;//将该顶点纳入MST中

for(intj=1;jnum_vexs;j++){

if(lowcost[j]!=0&&g->arc[min_k][j]lowcost[j]=g->arc[min_k][j];//较小的权值存入lowcost相应位置

adjvex[j]=min_k;//这条较小权值的边的其中一个顶点,要求是在MST中已有的顶点,存入adjvex

}

}

//把lowcost和adjvex准备好后,进入下一轮循环后遍历lowcost输出顶点对

}

delete[]adjvex;

delete[]lowcost;

}

算法的时间复杂度为O(n^2)

输出

01

05

18

82

16

67

74

73