prim算法

prim算法的基本思想:

从连通网N={V,E}中的某一顶点U0出发,选择与它关联的具有最小权值的边(U0,v),将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去,直到网中的所有顶点都加入到生成树顶点集合U中为止。

由于和dijkstra差不多,所以用邻接矩阵存储;

模板(低智商的我果断的把他取了个名字==)

 

原文地址:https://www.cnblogs.com/20003238wzc--/p/4746315.html