最小生成树

最小生成树 最小生成树

连通图：

在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。

生成树：

一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。只要能连通所有顶点而又不产生回路的任何子图都是它的生成树。

最小生成树：

设G=(V，E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价，在G的所有生成树中，代价最小的生成树称为最小生成树。

prim算法

思想：最近点的贪心策略。

与朴素版dijkstra算法十分的相像，区别在于Dijkstra算法是更新到起始点的距离，Prim是更新到集合S的距离

【步骤】

prim算法任选一点作为开始，为了与dijkstra向类比，我们选第一个点为起点

初始化距离，dist[1] = 0， 其它为无穷

找到不在集合s中的 且 距离集合s最近的点t

​ t <— j。如存在不连通的点 ，则说明不是生成树自然也构不成最小生成树。

​ 更新权重之和(res)；将t加入集合s

​ 用t去更新其它点到集合s的距离

返回res

一些注意事项：

从第一个节点开始：

为了与前面学习的的Dijkstra算法相照应，方便记忆

更新权重写在前面：

写在前面，如果一个节点本身出现负环，下面这句更新后，会影响结果，比如g[t] [j],当t = j,更新了g[t][t],影响res结果

【核心代码】

时间复杂度：O(n * n)

//存储方式：邻接矩阵
int g[N][N];//存图：若存在重边，取小者
int dist[N];//储存点到集合的最短距离
bool st[N];//集合s
int prim()
{
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	
	int res = 0;
	for(int i = 0; i < n; i ++)
	{
		int t = -1;
		for(int j = 1; j <= n; j ++)//找到不在集合中且距离集合最近的点
		{
			if(!st[j] & (t == -1 || dist[t] > dist[j]))
				t = j;
		}
		if(dist[t] == 0x3f3f3f3f) return -1;// 不连通
		
        //更新权重之和；加入集合
		res += dist[t];
		st[t] = true;
		
        //用t更新其它点到 集合s 的距离
		for(int j = 1; j <= n; j ++) dist[j] = min(dist[j], g[t][j]);
	}
	return res;
}

kruskal算法

思想：最短边的贪心策略。

思路：

Kruskal算法为了提高每次贪心选择时查找最短边的效率，可以先将图G中的边按代价从小到大排序，则这个 *** 作的时间复杂度为O(eloge)，其中e为无向连通网中边的个数。对于两个顶点是否属于同一个连通分量，可以用并查集的 *** 作将其时间性能提高到O(e)，所以，Kruskal算法的时间性能是O(eloge)。

【步骤】

将所有的边按权重从小到大排序O(elog(e))

枚举每条边a,b，权重为c

if a,b两点不连通 O(e)

将 a,b边加入集合中

注意：

（1） *** 作2，判断是否为同一个连通分量；合并顶点——>并查集

（2）需要使用变量cnt来记录加入集合的边数，若cnt < n - 1表明不能遍历所有点（边集不是n-1条，说明n个点中存在不连通的点，即不是生成树，自然也不是最小生成树！）

【核心代码】

int p[N];// 存储祖宗节点编号 

//结构体存边
struct Edge
{
    int a, b, w;
    bool operator< (const Edge &W)const //重载：按权重排序
    {
        return w < W.w;
    } 
}edges[M];
//并查集判断是否连通
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
//kruskal()实现
int kruskal()
{
    sort(edges, edges + m); // 将边升序排序
    
    // 初始化并查集
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    
    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ ) // 每轮拿到最短边
    {
        int a = edges[i].a, b = edges[i].b,  w = edges[i].w;
        
        //如果 a,b两点不连通，则合并
        a = find(a), b = find(b);
        if(a != b)
        {
            p[a] = b;
            res += w;
            cnt ++;
        }
    }
    
    if(cnt < n - 1) return INF;
    return res;
    
}

【b站某位大佬的视频讲解】最小生成树