最小生成树

最小生成树,第1张

最小生成树 最小生成树

连通图:

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

生成树:

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

最小生成树:

G=(VE)是一个无向连通网,生成树上各边的权值之和称为该生成树的代价,在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站某位大佬的视频讲解】最小生成树

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5713685.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存