最小生成树

原文链接：https://blog.csdn.net/u011815404/article/details/84070642
原文链接：https://blog.csdn.net/u011815404/article/details/88625323
原文链接：https://blog.csdn.net/u011815404/article/details/88625346

【概述】

对一个具有 $n$n 个点的连通图进行遍历，对于遍历后的子图，其包含原图中所有的点且保持图连通，最后的结构一定是一个具有 $n-1$n−1 条边的树，通常称为生成树。

在生成树问题中，最常见的问题就是最小生成树问题，所谓最小生成树，就是对于一个有 $n$n 个点的无向连通图的生成树，其包含原图中的所有点，且保持图连通的边权总和最少的边。

简单来说，对于一个有 $n$n 个点的图，边一定是大于等于 $n-1$n−1 条的，最小生成树，就是在这些边中选择 $n-1$n−1 条出来连接所有的 $n$n 个点，且这 $n-1$n−1 条边的边权之和是所有方案中最小的。

最小生成树具有以下两条性质：

1. 切割性质：连接点 x、y 的边权最小的边必定被生成树包含
2. 回路性质：任意回路/环上的边权最大的边必不被生成树包含

求最小生成树一般有 Prim 算法与 Kruskal 算法，其中，Prim 算法时间复杂度为 O(V*V)，与图中边数无关，适合稠密图；Kruskal 算法时间复杂度为O(ElogE)，需要对图的边进行访问，适合稀疏图。

【Prim算法】

【基本思想】

Prim 算法基本思想是蓝白点思想，用白点代表已进入最小生成树的点，蓝点代表未进入最小生成树的点。

每次循环都将一个蓝点 $u$u 变为白点，并且此蓝点 $u$u 与白点相连的最小边权 $min[u]$min[u] 还是当前所有蓝点中最小的。这相当于每次循环让一个新的点加入生成树，让一条最小边加入生成树，$n-1$n−1 次循环就能生成一棵含有 $n$n 个点的树，最后得到的一定是最小生成树。

其时间复杂度为：O(N*N)，N 代表点数。

【算法分析】

以下图为例，蓝点和虚线代表未进入最小生成树的点、边，白点和实线代表已进入最小生成树是点、边。

初始时，所有点都是蓝点，$min[1]=0，min[2、3、4、5]=INF$min[1]=0，min[2、3、4、5]=INF，权值和 $MST=0$MST=0。

第一次循环找到 $min[1]=0$min[1]=0 最小的蓝点 $1$1。将 $1$1 变为白点，接着枚举与 $1$1 相连的所有蓝点 $2、3、4$2、3、4，修改它们与白点相连的最小边权。故有：$min[2]=w[1][2]=2，min[3]=w[1][3]=4，min[4]=w[1][4]=7，MST=0$min[2]=w[1][2]=2，min[3]=w[1][3]=4，min[4]=w[1][4]=7，MST=0。

第二次循环是找到 $min[2]$min[2] 最小的蓝点 $2$2。将 $2$2 变为白点，接着枚举与 $2$2 相连的所有蓝点 $3、5$3、5，修改它们与白点相连的最小边权。故有：$min[3]=w[2][3]=1，min[5]=w[2][5]=2，MST=2$min[3]=w[2][3]=1，min[5]=w[2][5]=2，MST=2。

第三次循环是找到 $min[3]$min[3] 最小的蓝点 $3$3。将 $3$3 变为蓝点，接着枚举与 $3$3 相邻的所有蓝点 $4、5$4、5，修改它们与白点相连的最小边权。故有：$min[4]=w[3][4]=1$min[4]=w[3][4]=1，由于 $min[5]=2<w[3][5]=6$min[5]=2<w[3][5]=6，所以不修改 $min[5]$min[5] 的值，$MST=3$MST=3。

最后两轮循环将点 $4、5$4、5 以及边 $w[2][5]、w[3][4]$w[2][5]、w[3][4] 添加进最小生成树。

最后权值之和 $MST=6$MST=6。

【算法描述】

以 $1$1 为起点生成最小生成树，$vis[v]$vis[v] 代表 $v$v 点是否加入最小生成树中，$min[v]$min[v] 代表蓝点 $v$v 与白点相连的最小边权，$MST$MST 代表最小生成树边权之和。

初始化：

  $vis[1...n]=false，MST=0$vis[1...n]=false，MST=0

  $min[v]=INF（v≠1），min[1]=0$min[v]=INF（v​=1），min[1]=0

主体

void Prim()
{
    for(int i = 1; i <= n; i++)
    {
        int u = 0;
    
        for(int j = 1; j <= n; j++)					//枚举所有点
            if(vis[j]==false && min[j]<min[u])		//寻找与白点相连的权值最小的蓝点u
                u = j;
        vis[u] = true;								//蓝点u加入生成树，标记为白点
    
        for(int j = 1; j <= n; j++)					//修改所有与u相连的蓝点
        	if(vis[j]==false && g[u][j]<min[j])
                min[j] = g[u][j];
    }
 
    //权值和的计算
    int MST = 0;
    for(int i = 1; i <= n; i++)
        MST += min[i];
}

【模板】

int n, m;			//n个点m条边
int G[N][N];
int dis[N];
bool vis[N];
int MST;

void Prim()
{
    for(int i = 1; i <= n; i++)
	{
        int k;
        int minn = INF;
        for(int j = 1; j <= n; j++)		//枚举所有点
		{
            if(!vis[j]&&dis[j]<minn)	//寻找与白点相连的权值最小的蓝点u
			{
                minn = dis[j];
                k = j;
            }
        }
        vis[k] = true;						//蓝点u加入生成树，标记为白点
        for(int j = 1; j <= n; j++)			//修改所有与u相连的蓝点
            if(!vis[j]&&dis[j]>G[k][j])
                dis[j] = G[k][j];
    }
 
    MST = 0;
    for(int i = 1; i <= n; i++)				//权值和的计算
        MST += dis[i];
}
 
int main()
{
    cin>>n>>m;
    memset(vis, false, sizeof(vis));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin>>G[i][j];
    for(int i = 1; i <= n; i++)
        dis[i] = G[1][i];
    Prim();
    cout<<MST<<endl;
    return 0;
}

【Kruskal算法】

【基本思想】

Kruskal 算法基本思想是并查集思想，将所有边升序排序，并认为每一个点都是孤立的，分属 $n$n 个独立的集合。

按顺序枚举每一条边，如果这条边连接的两个点分属两个不同的集合，那么就将这条边加入最小生成树，这两个不同的集合合并为一个集合；如果这条边连接的两个点属于同一集合，那么就跳过。直到选取 $n-1$n−1 条边为止（只剩一个集合）。

其时间复杂度为：O(E*logE)，E 代表边数。

【算法分析】

以下图为例

开始时，$5$5 个集合$｛｛1｝，｛2｝，｛3｝，｛4｝，｛5｝｝$｛｛1｝，｛2｝，｛3｝，｛4｝，｛5｝｝，生成树中没有边，$MST=0$MST=0。

第一次选择 $<1,2>$<1,2> 这条边，将边加入生成树中，将两个顶点 $1、2$1、2 合并为一个集合。

此时，有 $4$4 个集合$｛｛1,2｝，｛3｝，｛4｝，｛5｝｝$｛｛1,2｝，｛3｝，｛4｝，｛5｝｝，$1$1 条边$｛<1,2>｝$｛<1,2>｝，$MST=2$MST=2。

第二次选择的是 $<4，5>$<4，5> 这条边，将这条边加入生成树中，将两个顶点 $4、5$4、5 合并为一个集合。

此时，有 $3$3 个集合$｛｛1，2｝，｛3｝，｛4，5｝｝$｛｛1，2｝，｛3｝，｛4，5｝｝，$2$2 条边$｛<1，2>，<4，5>｝$｛<1，2>，<4，5>｝，$MST=5$MST=5。

第三次选择的是 $<3，5>$<3，5> 这条边，将这条边加入生成树中，将它的两个顶点 $3、5$3、5 所在的两个集合合并为一个集合。

此时，有 $2$2 个集合$｛｛1，2｝，｛3，4，5｝｝$｛｛1，2｝，｛3，4，5｝｝，$3$3 条边$｛<1，2>，<4，5>，<3，5>｝$｛<1，2>，<4，5>，<3，5>｝，$MST=11$MST=11。

第四次选择的是 $<2，5>$<2，5> 这条边，将这条边加入到生成树中，将它的两个顶点 $2、5$2、5 所在的两个集合合并为一个集合。

此时，有 $1$1 个集合$｛1，2，3，4，5｝$｛1，2，3，4，5｝，$4$4 条边$｛<1，2>，<4，5>，<3，5>，<2，5>｝，MST=19$｛<1，2>，<4，5>，<3，5>，<2，5>｝，MST=19。

【算法描述】

struct Edge {
    int u, v, w;
    bool operator <(Edge K)const {
        return w<K.w;
    }
}edge[N];

int n, m;
int father[N], res;
int mst = 0;

int Find(int x)
{
    if(father[x]==x)
        return x;
    return father[x] = Find(father[x]);
}

void kruskal()
{
    for(int i = 1; i <= n; ++i)
      father[i] = i;
    sort(edge+1, edge+m+1);
    for(int i = 1; i <= m; ++i)
	{
        int f1 = Find(edge[i].u);
        int f2 = Find(edge[i].v);
        if(f1==f2)
            continue;
        father[f2] = f1;
 
        mst++;
        if(mst==n-1)
		{
            res = edge[i].w;
            return;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i)
      scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
    kruskal();
    printf("%d\n", res);
    return 0;
}