Prim算法的实现过程？

G=（V,E）

①初始化：读入的数据用邻接矩阵x存储，一个一维布尔型数组chosen，记录第i个节点是否已选，初始值除1外全部设为false，记录权值的变量cost赋值为0；

以下②到④循环执行v-1次（每次生成一条边，运行（点的个数减1）次后，生成一棵最小生成树）：

②临时变量p赋值为无限大，用于记录当前最小值；

③二重循环（外循环i，内循环j）扫描邻接矩阵：如果chosen[i]=true（也就是说第i个点已选），那么扫描x[i]，如果not(chosen[j])（也就是说第j个点未选），那么如果x[i,j]<p，那么p赋值为x[i,j],临时变量q赋值为j

④把cost赋值为cost+o，把chosen[q]赋值为true（也就是说第j个点已选）；

⑤输出cost。

一、以上给出具体的运行过程。这个算法的策略就是贪心，和dijkstra差不多，每次都选择未选的边中权值最小的那一条，直到生成最小生成树。用chosen的目的就是保证生成过程中没有环出现，也就是说保证选择的边不会通向一个已经包含在生成树中的点。

二、这个只输出猛衡最小生成树的每条边权值之和，如果要输出整棵最小生成树，加一个[1..n,1..2]的数组，在第④步的时候把每次选的边记录下来就可以了。

三桐知早、用小顶堆在第③步优化一下的话就不用每局雀次都扫描那么多边了，只不过建堆维护堆代码写起来很麻烦。

四、prim适合用于比较稠密的网，点数和边数差不多的时候效率很恶心，一般都用kruskal。

你要先明白prim算法的原理，明白原理后看下面的程序要点：

1.程序实现的时候将点分成两部分，加入集合的和没棚念有加入集合的；

2.每次从没有加入集合中找点；

3.对所有没岩裤有加入到集链枣困合中的点中，找一个边权最小的；

4.将边权最小的点加入集合中，并且修改和加入点相连的没有加入的点的权，重复第2步，知道所有的点都加入到集合中；

算法同样是解决最小生成树的问题。

其算法为：在这n个点中的相通的边进行排序，然后不断地将边添加到集合中（体现了贪心的算法特点），在并入集合之前，必须检查一下这两点是不是在一个集合当中，这就用到了并查集的知识。直到边的集合达到了n-1个。

与prim算法的不同：prim算法为单源不断寻找连接的最短边掘亏雹，向外扩展，即单树形成森林。而Kruskal算法则是不断寻找最短边然后不断将集合合并，即多树形成森林。

复杂度的不同：prim算法的复杂度是O(n^2),其中n为点的个数。Kruskal算法的复杂度是O(e*loge)，其中e为边的个数。两者各有优劣，在不同的情况下选择不同的算法。

Prim算法用于求无向图的最小生成树

设图G =（V，E），其生成树的顶点集合为U。

①、把v0放入U。

②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。

③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。

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

Prim算法实现：

（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对空悉应顶点不在集判帆合中（注意：顶点号与下标号差1）

（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。

{先选定一个点，然后从该点出发，与该点相连的点取权值最小者归入集合，然后再比较在集合中的两点与其它各点的边的权值最小者，再次进入集合，一直到将所有的点都归入集合为止。}

---