生成树

       一个连通图（如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径））的生成树是该连通图的一个极小连同子图,它含有图中全部顶点,和构成一棵树的(n-1)条边.如果在一棵生成树上添加任何一条边,必定构成一个环,因为这条边使得它依附的那两个顶点之间有了第二条路径.一棵有n个顶点的生成树(连通无回路图)有且仅有(n-1)条边,但是,有(n-1)条边的图不一定都是生成树.如果一个图有n个顶点和小于(n-1)条边,则是非连通图;如果它有多于(n-1)条边,则一定有回路.

最小生成树

    对于一个带权(假定每条边上的权值均为大于零的实数)连通无向图G中的不同生成树,各树的边上的权值之和可能不同；图中所有生成树中具有边上的权值之和最小的树称为该图的最小生成树.

    按照生成树的定义,n个顶点的连通图的生成树有n个顶点和(n-1)条边.因此构造最小生成树的准则有三条:
(1) 必须只使用该图中的边来构造最小生成树;
(2) 必须使用且仅使用(n-1)条边来连接图中的n个顶点;
(3) 不能使用产生回路的边.

举个栗子

（这是一个无向图）

其中a，b，c，d，e（b有一条线画错了，画图工具实在难用，就不改了，你们能看出来就行）都是无向图的生成树，但是只有d是它的最小生成树，因为它的所有边的权值之和最小。

下面通过一个具体问题展开对最小生成树的讲解

问题

    假设要在n个城市之间建立通讯联络网则连通n个城市只需要修建n-1条路线，如何在最节省经费的前提下建立这个通讯网？

该问题等价于

    构造网的一颗最小生成树，即在e条带权的边中选取n-1条边（不构成回路），使“权值之和” 最小。

    算法一：Prime

    算法二：Kruskal

Prime算法

    在带权连通图中V是包含所有顶点的集合，U是已经在最小生成树中的节点；

    （1）初始时，从图中任意某一顶点v开始，此时集合U={v}（以v到其他顶点的所有边为侯选边）；

    （2） 在所有u∈U,w∈V-U的边(u,w)∈E中找到一条权值最小的边，将(u,w)这条边加入到已找到边的集合，并且将点w加入到集合U中，

    （3）重复上一操作，当U=V时，就找到了这颗最小生成树。

    核心步骤：在所有u∈U,w∈V-U的边(u,w)∈E中找到一条权值最小的边。

 知道了Prime算法的核心步骤，下面我们就用图示法来演示一下工作流程，如图：下图是一个带权连通图，要找它的最小生成树。

1.首先，确定起始顶点。我以顶点A作为起始点。根据查找法则，与点A相邻的点有点B和点H，比较AB与AH，我们选择点B，如下图。并将点B加入到U中。

2.继续下一步，此时集合U中有{A,B}两个点，再分别以这两点为起始点，根据查找法则，找到边BC（当有多条边权值相等时，可选任意一条），如下图。并将点C加入到U中。

3.继续，此时集合U中有{A,B,C}三个点，根据查找法则，我们找到了符合要求的边CI，如下图。并将点I加入到U中。

4.继续，此时集合U中有{A,B,C,I}四个点，根绝查找法则，找到符合要求的边CF，如下图。并将点F加入到集合U中。

5.继续，依照查找法则我们找到边FG,如下图。并将点G加入到U中。

6.继续，依照查找法则我们找到边GH,如下图。并将点H加入到U中。

7.继续，依照查找法则我们找到边CD,如下图。并将点D加入到U中。

8.继续，依照查找法则我们找到边DE,如下图。并将点E加入到U中。此时，满足U = V，即找到了这颗最小生成树。

Prime核心代码：

int Prime(int v)///最小生成树的起点v
{
    sum = 0;
    for(int i = 1; i <= n; i++)
        d[i] = dis[v][i];
    d[v] = 0;
    flag[v] = 1;///flag用来标记是否遍历过
    for(int i = 1; i < n; i++)///一共n个点，要找n-1条边
    {
        int minn = INF,k;
        for(int j = 1; j <= n; j++)///在所有u∈U,w∈V-U的边(u,w)∈E中找到一条权值最小的边
        {
            if(minn > d[j] && flag[j] == 0)
            {
                k = j;
                minn = d[j];
            }
        }
        flag[k] = 1;///将此点加入最小生成树中
        sum += d[k];
        for(int j =1; j <= n; j++)///更新不在最小生成树的点的边权值，以便找到下一个权值最小的边
        {
            if(flag[j] == 0 && d[k] > dis[m][k])
                d[k] = dis[m][k];
        }
    }
    return sum;///返回生成的最小生成树的权值和
}

Kruskal算法

        克鲁斯卡尔算法的基本思想是以边为主导地位，始终选择当前可用（所选的边不能构成回路）的最小权植边。所以Kruskal算法的第一步是给所有的边按照从小到大的顺序排序。这一步可以直接使用库函数qsort或者sort。接下来从小到大依次考察每一条边（u，v）。

具体实现过程如下：

（1）设一个有n个顶点的连通网络为G（V,E），最初先构造一个只有n个顶点，没有边的非连通图T={V,空}，图中每个顶点自成一格连通分量。

（2）在Ｅ中选择一条具有最小权植的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入到Ｔ中；否则，即这条边的两个顶点落到同一连通分量上，则将此边舍去（此后永不选用这条边），重新选择一条权植最小的边。

（3）如此重复下去，直到所有顶点在同一连通分量上为止。

     下面是克鲁斯卡尔算法的示例图演示                   

      

        上面提到了“连通分量的查询和合并”，这就牵扯到了并查集的知识。基本的处理思想是：初始时把每个对象看作是一个单元素集合；然后依次按顺序读入联通边，将连通边中的两个元素合并。在此过程中将重复使用一个搜索（Find）运算，确定一个集合在哪个集合中。当读入一个连通边（ｕ，ｖ）时，先判断ｕ和ｖ是否在同一个集合中，如果是则不用合并；如果不是，则用一个合并（Union）运算把ｕ、ｖ所在集合合并，使得这两个集合中的任意两个元素都连通。因此并查集在处理时，主要用到搜索和合并两个运算。

Kruskal核心代码：

struct Edge
{
    int s,e;///s记录起点，e记录终点
    double dis;///dis记录起点到终点的距离
}e[5555];
int cmp(Edge a,Edge b)
{
    return a.dis < b.dis;///按距离从小到大排列
}
int father(int x)///找父亲节点，用于判断是否在一个集合中
{
    if(x == fa[x]) return x;
    else
    {
        int root = father(fa[x]);
        fa[x] = root;
        return root;
    }
}
int Kruskal()
{
    for(int i = 1; i <= n; i++)
        fa[i] = i;
    sort(e,e+cunt,cmp);///按从小到大对所有边进行排序
    double ans = 0;
    for(int i = 0; i < cunt; i++)///遍历所有的边
    {
        int a = father(e[i].s);
        int b = father(e[i].e);
        if(a != b)
        {
            ans += e[i].dis;
            fa[a] = b;///合并集合
        }
    }
    return ans;///返回最小生成树的权值和
}

  例题：畅通工程再续

两算法比较：

Prime算法：时间复杂度为O（n^2），其中n为顶点的个数；它的执行时间与图中的边数无关，因此，普利姆算法适合于稠密图。

Kruskal算法：时间复杂度为elog2e，其中e为边的个数；他的执行时间与图中边数有关，因此，克鲁斯卡尔算法适合于稀疏图。

 ~  over     终于可以收工嘞~~~

写的不清楚的地方欢迎各位大佬留言讨论。