案例引入

      校园网布线如何设计网络电缆布线，将各个单位连通起来，并使费用最少呢?对于n个顶点的连通图，只需n-1条边就可以使这个图连通n-1条边要想保证图连通，就必须不含回路，所以只需要找出n-1条权值最小且无回路的边即可。
 

对于最小生成树的原理就不解释了，离散数学都学了 ~_~，我们的重点是如何判断是否有回路。这里有一个方法——集合避圈法。

---

Prim算法

把已经在生成树中的节点看做一个集合，剩下的节点看作另一个集合，哎！看到这里是不是和我们之前接触过的Dijkstra算法十分相似呢？之后从连接两个集合的边中选择一条权值最小的边。

照常我们把整个集合设为V，选过的节点的集合为U，剩下的自然为V-U。

设置两个数组：

closest[j]：表示V-U中的顶点j到集合U中的最临近点。

lowcost[j]：表示V-U中的顶点j到集合U中的最邻近点的边值，即边(j, closet[j])的权值。

解释一下这张图以及数组的具体实现方法：假设我们选完2节点了，那么在V-U集合中与U相邻的只有3，7，6节点，先看3节点，只有和2节点相邻，所以closest[3] = 2，lowcost[3] = 20。7节点与1，2都相邻，那么我们找最短的权值，与2相连，故closest[7] = 2，lowcost[7] = 1，6节点同理。在此次划分中没有能与U集合相连的依然为无穷（PS:初始化就是无穷）。之后在lowcost数组中的V-U集合中的节点权值进行排序，得出节点7权值最小，把7划入U集合，更新两个数组重复即可。

算法实现

const int inf = 0x3f3f3f3f;
const int N = 1000;
int c[N][N],closest[N],lowcost[N],ans[N];// c数组为邻接矩阵来存图
bool s[N];// 判断某节点是否加入U集合
int n,m;
int prim(int n){
    s[1]=true;// 从任意接节点开始都可，默认1
    lowcost[1]=0;
    for(int i=2;i<=n;i++){// 初始化数组
        lowcost[i]=c[1][i];
        closest[i]=1;
        s[i]=false;
    }
    for(int i=1;i// 重复n-1次
        int temp = inf;
        int t = 1;// 节点编号
        for(int j=1;j<=n;j++){// 找最小
            if(!s[j]&&lowcost[j]// 节点为V-U中的，且与U邻接
                t=j;
                temp=lowcost[j];// 更新，temp变成存最小值
            }
        }
        if(t==1){// 找不到返回0
            return 0;
        }
        s[t]=true;
        for(int j=1;j<=n;j++){// 最后再更新一边
            if(!s[j]&&c[t][j]
                lowcost[j]=c[t][j];
                closest[j]=t;
            }
        }
    }

---

Kruskal算法

将n个顶点看成是n个孤立的连通分支，首先将所有的边按权值从小到大排序，然后做贪心选择：在边集E中选取权值最小的边(i, j），如果将边（i, j）加入集合TE中不产生回路（圈），则将边(i, j）加入边集TE中;否则继续选择下一条最短边。

这里我们可以看出与Prim算法的区别了，这个是以边为选取目标，所以存图的方式为边集数组。

此算法的初始化的步骤：先将边集E中的所有边按权值从小到大排序，边集TE={}，每个顶点初始化一个集合号。然后寻找最小边（i，j）。什么是转化成以一个集合号？

 

假设我们已经把节点7与2合并，那么7的编号就要与2相同 ；之后我们应该连接4和5，此时编号都应该成为4或者5；然后连接3和2（7），3的编号变为2，以此类推。

算法实现

int fa[N];
int n,m;
struct Edge{
    int u,v,w;
}e[N*N];
bool cmp(Edge x,Edge y){// 按边值进行升序排序
    return x.w
}
void init(int n){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}
int find(int x){// 使用并查集合并集合
    if(x!=fa[a]){
        fa[x]=find(fa[x]);
    }
    return fa[a];
}
bool change(int a,int b){// 改边操作，传入两个数比较
    int p=find(a);
    int q=find(b);
    if(q==p){// 比较集合号
        return false;
    }
    fa[q] = p;
    return true;
}
int Kruskal(int n){
    int ans = 0,cnt=0;
    for(int i=0;i
        if(change(e[i].u,e[i].v)){
            ans+=e[i].w;
            cnt++;
            if(cnt==n-1){
                return ans;
            }
        }
    }
    return 0;
}