适用范围：要求无向图

prim算法（读者可以将其读作“普里姆算法”）用来解决最小生成树问题，

其基本思想是：

·对图G（VE）设置集合S，存放已被访问的顶点，

·然后每次从集合V-S中选择与集合S的最短距离最小的一个顶点（记为u），访问并加入集合S。

·令顶点u为中介点，优化所有从u能到达的顶点v与集合S之间的最短距离。

这样的操作执行n次（n为顶点个数），直到集合S已包含所有顶点。可以发现，prim算法的思想与最短路径中Dijkstra算法的思想几乎完全相同，只是在涉及最短距离时使用了集合S代替Dijkstra算法中的起点s。

 1 int prim()
 2 
 3 {//默认0号为初始点，函数返回最小生成树的边权之和
 4 
 5     fi11(d，d+MAXV，Inf)；//fi11函数将整个d数组赋为INE (慎用memset )
 6 
 7     d[0]=0；//只有0号顶点到集合s的距离为0，其余全为Inf
 8 
 9     int ans=0；//存放最小生成树的边权之和
10 
11     for (int i=0；i<n；i++ )
12 
13    {//循环n次
14 
15         int u=-1，MIN=Inf；//u使d[u]最小，MIN存放该最小的d[u]
16 
17         for (int j=0；j<n；j++ )
18 
19         {//找到未访问的顶点中d[]最小的
20 
21             if (vis[j]==false && d[j]<MIN )
22 
23             {
24 
25                 u=j；
26 
27                 MIN=d[j]；
28 
29             }
30 
31         }
32 
33         //找不到小于Inf的d[u]，则剩下的顶点和集合s不连通
34 
35         if (u==-1 )
36 
37             return-1；
38 
39         vis[u]=true；//标记u为已访问
40 
41         ans += d[u]；//将与集合s距离最小的边加入最小生成树
42 
43         for (int v=0；v<n；v++ )
44 
45         {//v未访问&&u能到达v&&以u为中介点可以使v离集合S更近
46 
47             if (vis[v]==false && G[u][v] ！= Inf && G[u][v]< d[v] )
48 
49                 d[v]=G[u][v]；//将G[u][v]赋值给d[v]
50 
51         }
52 
53     }
54 
55     return ans；//返回最小生成树的边权之和
56 
57 }