图论入门（九）Prim算法

转载自https://blog.****.net/saltriver/article/details/72571114

前面说过，Prim算法是从顶点着手构建最小生成树的。应该说，Prim算法比Kruskal更简单。我们还是以前面的乡镇假设光纤网络为例：

Prim算法工作步骤

（1） 构建全部顶点集V，选取初始顶点，加入顶点集U。

构建顶点集V={a,b,c,d,e,f,g,h,i}，从中选取任意一个顶点。我们假设从顶点a开始。将a加入到顶点集U={a}中。

（2） 找U中顶点与V-U中顶点的所有边。

（3） 选取所有边中的最短边加入最小生成树。

（4） 将最短边另一头的顶点，加入顶点集合U。

（5） 继续找U中顶点与V-U中顶点的所有边。

（6） 继续选取最短边，将最短边加入最小生成树，并将最短边另一头顶点加入U。

（7） 如此循环反复，直至U=V。

 

为什么不会构成环？

因为我们在寻找边时，只是找U与V-U中顶点所构成的边，而U中内部顶点的边是不会找的。找到最短边后，直接将另一头顶点加入U了，也就是说这两个顶点都在U中了，即使这2个顶点还有其他路径，后面都不会再找，也就不会构成回路了。

我也觉得黑黑的好丑