一、Prim算法 Prim算法采用与Dijkstra、Bellman-Ford算法一样的“蓝白点”思想：白点代表已经进入最小生成树的点，蓝点代表未进入最小生成树的点。 算法描述： 以1为起点生成最小生成树，min[v]表示蓝点v与白点相连的最小边权。 MST表示最小生成树的权值之和。 a）初始化：min[v]= ∞(v≠1); min[1]=0;MST=0; b）for (i = 1; i<= n; i++) 1.寻找min[u]最小的蓝点u。 2.将u标记为白点 3.MST+=min[u] 4.for 与白点u相连的所有蓝点v if (w[u][v]<min[v]) min[v]=w[u][v]; c）算法结束： MST即为最小生成树的权值之和
算法分析&思想讲解： Prim算法每次循环都将一个蓝点u变为白点，并且此蓝点u与白点相连的最小边权min[u]还是当前所有蓝点中最小的。这样相当于向生成树中添加了n-1次最小的边，最后得到的一定是最小生成树。 我们通过对下图最小生成树的求解模拟来理解上面的思想。蓝点和虚线代表未进入最小生成树的点、边；白点和实线代表已进入最小生成树的点、边。 初始时所有点都是蓝点，min[1]=0,min[2、3、4、5]=∞。权值之和MST=0。 第一次循环自然是找到min[1]=0最小的蓝点1。将1变为白点，接着枚举与1相连的所有蓝点2、3、4，修改它们与白点相连的最小边权。 最后两轮循环将点4、5以及边w[2][5],w[3][4]添加进最小生成树。 最后权值之和MST=6。 这n次循环，每次循环我们都能让一个新的点加入生成树，n次循环就能把所有点囊括到其中；每次循环我们都能让一条新的边加入生成树，n-1次循环就能生成一棵含有n个点的树；每次循环我们都取一条最小的边加入生成树，n-1次循环结束后，我们得到的就是一棵最小的生成树。 这就是Prim采取贪心法生成一棵最小生成树的原理。 算法时间复杂度：O (N2)。 二、Kruskal算法 Kruskal（克鲁斯卡尔）算法是一种巧妙利用并查集来求最小生成树的算法。 首先我们把无向图中相互连通的一些点称为处于同一个连通块中。 图中有3个连通块。1、2处于一个连通块中，4、5、6也处于一个连通块中，孤立点3也称为一个连通块。 Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。直到选取了n-1条边为止。 算法描述: 初始化并查集。father[x]=x。 tot=0 将所有边用快排从小到大排序。 计数器 k=0; for (i=1; i<=M; i++) //循环所有已从小到大排序的边 if 这是一条u,v不属于同一集合的边(u,v)(因为已经排序，所以必为最小)， begin ①合并u,v所在的集合，相当于把边(u,v)加入最小生成树。 ②tot=tot+W(u,v) ③k++ ④如果k=n-1,说明最小生成树已经生成，则break; end; 6. 结束，tot即为最小生成树的总权值之和。 思想讲解： Kruskal（克鲁斯卡尔）算法开始时，认为每一个点都是孤立的，分属于n个独立的集合。 Kruskal每次都选择一条最小的边，而且这条边的两个顶点分属于两个不同的集合。将选取的这条边加入最小生成树，并且合并集合。
