【数据结构基础整理】图05：普里姆算法详解

0x01.关于普里姆算法

普里姆算法&＃xff08;Prim算法&＃xff09;&＃xff0c;图论中的一种算法&＃xff0c;可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中&＃xff0c;不但包括了连通图里的所有顶点&＃xff08;英语&＃xff1a;Vertex (graph theory)&＃xff09;&＃xff0c;且其所有边的权值之和亦为最小。

0x02.生成树和最小生成树

既然普里姆算法是关于最小生成树的算法&＃xff0c;那么什么是什么是生成树和最小生成树呢&＃xff1f;

生成树定义&＃xff1a;

一个连通图的生成树是一个极小连通子图&＃xff0c;它含有图中全部n个顶点和n-1条边。

简单理解生成树&＃xff1a;

生成树简而言之就是由图去生成一颗树&＃xff0c;这颗树包含了图的全部顶点。

那么这里应该有几个生成树应该满足的条件&＃xff1a;

1.不能有任何闭合得部分&＃xff0c;因为闭合了就不叫树了。

2.得包含全部的顶点。

3.满足其它树的特征。

理解最小生成树&＃xff1a;

最小生成树&＃xff0c;就是生成一棵树&＃xff0c;所花费的代价最小&＃xff0c;也就是树所包含的所有边的权值和最小。

0x03.普里姆算法代码

由于是经典算法&＃xff0c;先看代码。

0x04.图解代码过程

下图是一个无向网图。顶点ABCDEFGHI分别是顶点表中的0~8号元素。

下面按照代码过程演示&＃xff1a;

代码第4&＃xff0c;5行创建了两个数组&＃xff0c;一个adjvex&＃xff0c;一个lowcost&＃xff0c;其中adjvex用于保存顶点的下标&＃xff0c;lowcost是整个普里姆算法的核心&＃xff0c;用于保存相关边的权值&＃xff0c;具体两个数组是如何存储的见下文。

代码第6&＃xff0c;7行分别对两个数组的0号下标进行初始化&＃xff0c;假设从A顶点开始&＃xff0c;lowcost[0]&＃61;0&＃xff0c;表示A已加入生成树&＃xff0c;可以这样理解&＃xff0c;lowcost中的某个数一旦被置为0&＃xff0c;说明这个下标所在顶点表中的顶点被纳入生成树了&＃xff0c;另外&＃xff0c;adjvex[0]&＃61;0的含义是假设从A开始。

代码第8~12行的循环表示对lowcost和adjvex数组赋值&＃xff0c;lowcost所赋的值是与A有关的边的权值&＃xff0c;adjvex所赋的值全部是0。

此时的lowcost为[0,8,32767,32767,32767,9,32767,32767,32767]。

此时的adjvex全部为0.

代码第15~17行&＃xff0c;将min设置为INTMAX&＃xff0c;目的是找到最小权值&＃xff1b;j设置为1&＃xff0c;作为下一个循环的循环变量&＃xff1b;k用来存储权值最小的顶点下标。

代码第18~26行的循环&＃xff0c;目的是寻找lowcost中权值最小的值&＃xff0c;和它对应的下标。

代码第27行&＃xff0c;输出了生成树中的第一条边&＃xff0c;此时的k表示的是lowcost中权值最小的边对应的顶点&＃xff0c;而adjvex[k]则表示这条边的另一个顶点&＃xff0c;在这也就是A。

代码第28行&＃xff0c;lowcost[k]&＃61;0&＃xff0c;表示顶点k已加入生成树&＃xff0c;对于locost中0的值&＃xff0c;以后都不进行操作。

代码第29~36行&＃xff0c;再进行一次循环&＃xff0c;此时的k&＃61;1&＃xff0c;那么这次循环的目的就是查找邻接矩阵中顶点B所对应的边的权值&＃xff0c;与之前lowcost中的值比较&＃xff0c;若有值更小&＃xff0c;则修改lowcost中的值&＃xff0c;并将k存入adjvex。

此时的lowcost为[0,0,16,32767,32767,9,14,32767,10]。

此时的adjvex为[0,0,1,0,0,0,1,0,1]。

第一遍大循环完成&＃xff0c;此时的生成树如图所示&＃xff08;红色部分&＃xff09;&＃xff1a;

我们发现一次大循环的目的就是找到一条权值最小的边加入最小生成树。

再来看第二次大循环。

由于第一次小循环的目的是找到lowcost中权值最小的值和顶点&＃xff0c;那么再经历第一次小循环后&＃xff0c;k应该等于值为9对于的下标&＃xff0c;也就是5&＃xff0c;而adjvex[5]&＃61;0&＃xff0c;所以此次加入的边应该是A--F。

第二次小循环的目的是改变lowcost中的值&＃xff0c;那么再经历第二次小循环&＃xff0c;此时k&＃61;5&＃xff0c;循环结束后&＃xff0c;lowcost应为[0,0,16,32767,24,0,14,32767,10]&＃xff0c;adjvex应为[0,0,1,0,5,0,1,0,1]。

此时的生成树为&＃xff1a;

再来第三次大循环&＃xff1a;

第一个小循环过后&＃xff0c;找到最小权值对于的下标k为8&＃xff0c;adjvex[8]&＃61;1&＃xff0c;也就是说边B--I加入生成树。

第二个小循换过后&＃xff0c;遍历k有关的边有没有比lowcost中的值小的&＃xff0c;循环过后&＃xff0c;lowcost应为[0,0,16,19,24,0,14,32767,0]&＃xff0c;adjvex应为[0,0,1,8,5,0,1,0,1].

此时的生成树为&＃xff1a;

第四次大循环&＃xff1a;

第一次小循环结束后&＃xff0c;k&＃61;6&＃xff0c;adjvex[6]&＃61;1,说明边B--G加入生成树。

第二次小循换结束后&＃xff0c;lowcost为[0,0,16,19,24,0,0,17,0]&＃xff0c;adjvex为[0,0,1,8,5,0,1,6,1]

此时的生成树如图&＃xff1a;

第五次大循环&＃xff1a;

第一次小循换后&＃xff0c;k&＃61;2&＃xff0c;adjvex[2]&＃61;2&＃xff0c;说明边B--C加入生成树。

第二次小循环后&＃xff0c;lowcost为[0,0,0,19,24,0,0,17,0]&＃xff0c;adjvex为[0,0,1,8,5,0,1,6,1]。

此时的生成树如图&＃xff1a;

第六次大循环&＃xff1a;

第一次小循换后&＃xff0c;k&＃61;7&＃xff0c;afjvex[7]&＃61;6,说明边G--H加入生成树&＃xff1b;

第二次小循换后&＃xff0c;lowcost为[0,0,0,14,5,0,0,0,0]&＃xff0c;adjvex为[0,0,1,7,7,0,1,6,1]。

此时的生成树为&＃xff1a;

第七次大循环&＃xff1a;

第一次小循换后&＃xff0c;k&＃61;5&＃xff0c;adjvex[5]&＃61;7&＃xff0c;说明边H--E加入生成树。

第二次小循换后&＃xff0c;lowcost为[0,0,0,14,0,0,0,0,0]&＃xff0c;adjvex为[0,0,1,7,7,0,1,6,1]。

此时的生成树为&＃xff1a;

第八次大循环&＃xff1a;

第一次小循换&＃xff0c;k&＃61;3&＃xff0c;adjvex[3]&＃61;7&＃xff0c;说明边H--D加入生成树。

第二次小循换&＃xff0c;lowcost全为0&＃xff0c;生成树已完成&＃xff0c;无意义。

此时的生成树为&＃xff1a;

代码到此执行完毕&＃xff0c;最小生生成树构造完成。

一个大循环里面两个小循环&＃xff0c;时间复杂度应为 O&＃xff08;e)&＃61;2e*e&＃xff1b;

0x05.原理深究

1.关于lowcost&＃xff0c;adjvex数组到底怎么理解。

lowcost是整个普里姆算法的核心部分&＃xff0c;它的含义就是存储各边的权值&＃xff0c;为0就代表&＃xff0c;该下标所对应的顶点已加入生成树&＃xff0c;不需要再考虑&＃xff0c;这个权值应该这样理解&＃xff0c;是对于已加入这棵生成树的顶点的所有边的最小权值&＃xff0c;这个最小指的是和这个权值下标连成的边的最小权值。

例如&＃xff0c;当第一次循环的时候&＃xff0c;lowcost为[0,8,32767,32767,32767,9,32767,32767,32767]。第一个0代表第一个顶点已加入生成树&＃xff0c;第二个8代表&＃xff0c;第二个顶点到已加入生成树的所有顶点之中权值最小的值&＃xff0c;那么如何知道在第二个小循换中&＃xff0c;改变了的话&＃xff0c;是对于第几个顶点来说的&＃xff0c;这个时候adjvex[k]的值就是对于第几个顶点而言&＃xff0c;比如&＃xff0c;此时的adjvex[2]&＃61;1&＃xff0c;代表8这个值是对于第二个顶点来说&＃xff0c;所有已加入生成树的顶点到这个顶点的最小权值。

lowcost每次在第一次小循换中&＃xff0c;会找出一个最小值出来&＃xff0c;并找到对应的顶点加入生成树。这个过程实际上就是找到所有顶点权值最小里面的最小。

lowcost中每有一个为0就是有一个顶点加入了生成树&＃xff0c;当所有顶点都加入后&＃xff0c;lowcost中的值都为0。

adjvex是存储相关顶点的下标的&＃xff0c;那么这个顶点下标究竟指的是什么呢&＃xff1f;我们可以看它是什么时候改变的呢&＃xff0c;就是在第二个小循换才开始改变的&＃xff0c;每次改变存的是一个权值对应的下标&＃xff0c;所以可以这样理解&＃xff0c;这个下标其实是与lowcost相同位置的值对应的&＃xff0c;是表示lowcost里这个权值是对于第几个顶点而言的最小值&＃xff0c;adjvex里的这个值和lowcost里那个数据对应的下标&＃xff0c;就是这个权值所代表的边的两个端点。

具体两个数组是何用处&＃xff0c;可以在不断的演练上述过程中发现规律。

2.对于第二个小循换而言&＃xff0c;为什么是找相对位置的小值。

也就是说如何理解代码 if (lowcost[j] !&＃61; 0 && G.edge[k][j]

这个原因其实就是lowcost中所存数据的意义&＃xff0c;是对于每个特定顶点的权值最小值&＃xff0c;而不是所有的最小值。

0x06.普里姆算法感悟