最小生成树

一、Prim算法

1.prim算法也被称为“加点法”，因为该算法是先从任意一顶点出发不断的选择目前距离最近且未被选择的点加入到已选的集合中，直到所有的点都被选到。（和最短路径中的Dijkstra算法很像）

2.prim算法的实现

• 首先将初始顶点u加入集合U中，然后用一个数组dis记录下其余点vj到顶点u的边权信息（dis[k]代表从u到k的权为dis[k])。
• 然后设置一个循环循环，循环n-1次即可。（n为顶点数所以要将每个点连接起来至少需要n-1条边）循环中先在dis数组中找到权值最小的顶点k，用一个变量累加这条边的权值。然后将这个顶点k加入集合U，相当于新增加了一条从k到j的边，再将dis数组更新为新的权值。

 3.prim算法的时间复杂度是O(n*n)与该网中的边数无关，因此适用于稠密图的最小生成树。

4.代码如下：

#include"stdio.h"
main()
{int n,m,i,j,k,min,t1,t2,t3;int e[7][7],dis[7],book[7]={0};int inf=99999999;int count=0,sum=0;scanf("%d %d",&n,&m);for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i==j) e[i][j]=0;else e[i][j]=inf;for(i=1;i<=m;i++){scanf("%d %d %d",&t1,&t2,&t3);e[t1][t2]=t3;e[t2][t1]=t3;}for(i=1;i<=n;i++)dis[i]=e[1][i];book[1]=1;count++;while(count<n){min=inf;for(i=1;i<=n;i++){if(book[i]==0&&dis[i]<min){min=dis[i];j=i;}}book[j]=1;count++;sum=sum+dis[j];for(k=1;k<=n;k++){if(book[k]==0&&dis[k]>e[j][k])dis[k]=e[j][k];} }printf("%d",sum);
} 

 二、kruskal算法

1.该算法为“加边法”，每一次都选择插入目前还未被加入最小生成树的一条边插入到最小生成树中，直到加入了n-1条边，将n个顶点相连。

2.kruskal算法实现：

• 将存储边的结构体数组（该结构体中有两个元素代表边的两个顶点）中的元素按权值从小到大排序。
• 每一次从排好序的数组中选出一条边，对这两个顶点进行判断看这两个点是否是分属于不同的连通分量，如果不等则合并这两个连通分量。如果它们属于同一个连通分量，则舍去这条边，选择下一条边进行判断。

3.关键代码如下：

  for(i=1;i<=m;i++)//开始从小到大枚举每一条边{if(merge(e[i].u,e[i].v))//判断一条边的两个顶点是否已经连通，即判断是否已在同一个集合中{count++;//如果目前尚未不连通，则选用这条边sum=sum+e[i].w;}if(count==n-1 ) break;//直到选用了n-1条边之后退出循环}

 三、prim算法和kruskal算法的区别

1.prim是加点法，每一次都选择增加一条边来建立一棵树。prim每次都是选择距离生成树最近的边。

2.Kruskal是加点法，按照从小到大的顺序去考察每一条边，每次都是先给最小边机会。

3.前者常用于稠密图，后者常用于稀疏图。