最小生成树基本算法

字数

820 字

阅读时间

4 分钟

---

基本算法介绍

最小生成树是针对无向连通图的

可用于生成最小生成树的算法有Prim算法和Kruskal算法，一般情况下，Kruskal使用更多，能使用Prim时可以用Kruskal，而使用Kruskal时不一定能使用Prim算法

Prim 算法的朴素做法：时间复杂度为 $O(n^2)$ Prim算法的堆优化版本完全不如Kruskal，所以如果有需要，则使用Kruskal算法

朴素Prim算法：使用邻接矩阵存储 Kruskal算法：时间复杂度为$O(m\log m)$，一般是直接存所有边（用一个三元组，即：结构体来存储）

原理证明：假设不选当前边，最终得到一颗树，然后将这条边加上，则必然会出现一个环，在这个环上，一定可以找出一条长度不小于当前边的边，那么把这条边替换上去，结果一定不会变差

Prim算法

已知一个联通块，每次将扩展一个距离联通块最近的点，直到扩展完所有点

int prim() {
    int res = 0;
    memset(dist, 0x7f, sizeof dist); // dist 为 double时，才使用 0x7f 作为最大值
    memset(st, 0, sizeof st);
    dist[1] = 0; // 点1作为初始点加入最小生成树联通块
    // dist[i]: 点 i 距离最小生成树连通块的最近距离

    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 (t == -1) break; // 图不连通,可不写这句判断
        st[t] = true;
        res += dist[t];
        for (int j = 1; j <= P; j++) { // 最好能有!st[j] 的判断，用于更新未加入最小生成树联通块的点，以防止某些情况下，不进行该判断会破坏原有最小生成树状态
            if (!st[j] && dist[j] > w[t][j]) { // 已加入联通块的节点不再更新其dist值，否则可能会破坏最小边权状态，所以不能变更为如下代码：for (int j = 1; j <= n; j ++) dist[j] = min(dist[j], w[t][j]);
                dist[j] = w[t][j]; // w[i][j]：点 i 和点 j 之间的距离
            }
        }
    }
    return res;
}

Kruskal算法

使用并查集优化

1. 将所有边权从小到大排序
2. 依次枚举每条边 u，v，w
   1. 如果u和v不连通，则将这条边加入到最小生成树

struct Edge
{
	int u, v, w; // 点u与点v之间的边，边权为w
	bool operator< (const Edge & t)const
	{
		return w < t.w; // 将 w 从小到大排序
	}
}e[N];

int p[N]; // 并查集
int ans, cnt;

int find(int x)
{
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}

bool Kruskal() // 返回是否存在最小生成树
{
	sort(e, e + m); // 已经存入了 m 条边
	for (int i = 1; i <= n; i ++) p[i] = i;

	for (int i = 0; i < m; i ++) // m 条边
	{
		int pa = find(e[i].u);
		int pb = find(e[i].v);
		if (pa != pb)
		{
			p[pa] = pb;
			ans += e[i].w; // 存储最小生成树的边权总和
			cnt ++; // 加入的边的条数
		}
	}

	return cnt == n - 1; // 似乎也可用于判断是否存在环？
}

贡献者

freeway348

文件历史

最后编辑于 4 天前查看完整历史

e587f-Update 简介梗概.md