最小生成树

发表于 更新于 分类于 ，
本文字数： 915
  • Prim求最小生成树
  • Kruskal求最小生成树

    Prim算法

思路

算法流程类似于Dijkstra，Prim是建立一个集合st[N]，将所有点（起点初始化为0）到该集合距离 dist 初始化为0x3f3f3f3f

n个点，一共遍历n次，每次寻找不在集合中距离集合最近的点（起点任意找），将其放入集合中，并用其更新其余所有点到集合的距离

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 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 false;
        res += dist[t]; //这里记录的是最小生成树的边权之和
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], g[t][j]);
        st[t] = true;
    }
    return true;
}

Kruskal算法

思路

  1. 将所有边按照权重从小到大排序（快排）
  2. 枚举每一条边，并检查边的起点与终点是否连通，如果不连通，则将这条边加入集合中（并查集）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for (int i = 1; i <= n; i++)
    p[i] = i;
sort(edge, edge + m);
for (int i = 0; i < m; i++)
{
    int a = edge[i].a, b = edge[i].b, w = edge[i].w;
    a = find(a), b = find(b);
    if (a == b)
        continue;
    else
    {
        p[a] = b;
        cnt++;
        res += w;
    }
}
if (cnt == n - 1) //cnt记录边数, n 个点对应n - 1条边
    cout << res;
else
    puts("impossible");