最小生成树

发表于 分类于 阅读次数： Disqus： 本文字数： 933 阅读时长 ≈ 3 分钟

简介

所谓最小生成树（minimum spanning tree），就是一个无向图的极小连通子图，包含原图中的所有节点，且所有边的权值之和最小。因其是一棵树，所以得名最小生成树。

听不懂？那我们来炒一颗栗子。 对于这个无向图： E.G. 下图就是它的最小生成树，边权和为\(2 + 2 + 3 = 7\)： 不过对于一部分图，比如上面炒的栗子，最小生成树有多种解，但是边权和是不变的：

代码

那么概念知道了，代码怎么写呢？
最小生成树有两种算法：Prim和Kruskal。在稠密图中，Prim比Kruskal优；但在稀疏图中，Kruskal比Prim优。

Prim

Prim的思想是：从任意一个节点开始，将已连接和未连接的节点各归为一类。每次找出一个与已连接节点之间边权最小的未连接节点，与其连接。将上述步骤重复\(n - 1\)次即可。
Prim每次要选择距离最短的一个节点，并用新的边更新其它节点的距离，这有点像最短路中的Dijkstra算法。

具体一点，就拿上面那颗栗子再炒一遍： E.G. 我们可以从\(1\)号点开始： Step 1 \(1\)可以连到\(2, 3, 4\)，但是\(1\)和\(2, 3\)两个点之间的边权是最短的，都是\(2\)，所以我们可以先连其中一个。边权一样，连哪个都无所谓： Step 2 连了\(2\)之后，边权最短的仍然是\(1 - 3\)，所以连上\(1\)和\(3\)： Step 3 现在只剩\(4\)最后一个点了。由于连接\(4\)的两条边\(1 - 4\)和\(3 - 4\)边权一样，所以连哪条都是正确的，最终结果就会有两个： Step 4 / 1 Step 4 / 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 建图
struct Edge {
    int from, to, dis;
    Edge(int _from, int _to, int _dis) {
        from = _from;
        to = _to;
        dis = _dis;
    }
};
std::vector<Edge> g[MAX_SIZE];
void insert(int u, int v, int w) {
    // 由于是无向图，所以要存两条边
    g[u].push_back(Edge(u, v, w));
    g[v].push_back(Edge(v, u, w));
}

// m是边数，n是节点数
int m, n;
int prim() {
    // now是选择的点，dis是now与其它点的距离，vis标记是否访问过
    int ans = 0, now = 1, dis[MAX_SIZE];
    bool vis[MAX_SIZE];
    // 初始化
    for (int i = 2; i <= n; ++i) {
        vis[i] = false;
        dis[i] = INF;
        for (int j = 0; j < int(g[i].size()); ++j)
            if (g[i][j].to == now)
                dis[i] = std::min(dis[i], g[i][j].dis);
    }

    for (int i = 1; i < node; ++i) {
        int minn = INF;
        vis[now] = true;
        // 找到边权最小的边，更新now
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && minn > dis[j]) {
                minn = dis[j];
                now = j;
            }
        }
        // 加上边权
        ans += minn;
        // 更新dis
        for (int j = 1; j <= n; ++j)
            for (int k = 0; !vis[j] && k < int(g[now].size()); ++k)
                if (dis[g[now][k].to] > g[now][k].dis)
                    dis[g[now][k].to] = g[now][k].dis;
    return ans;
}

Kruskal

Kruskal算法比较好理解，它的思想是将所有边按边权排序，然后选择边权最小的边，并依次连接。如果存在环（用并查集判断），就跳过这条边，直到加入了\(n - 1\)条边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
Edge g[MAX_SIZE];
int i = 0;
void insert(int u, int v, int w) {
    ++i;
    g[i].from = u;
    g[i].to = v;
    g[i].dis = w;
}

// 并查集
int fa[MAX_SIZE];
int find(int u) {
    if (fa[u] == u)
        return u;
    return fa[u] = find(fa[u]);
}

// 比较函数
bool cmp(Edge a, Edge b) {
    return a.dis < b.dis;
}
int kruskal() {
    // tot记录边数
    int ans = 0, tot = 0;
    // 排序
    std::sort(g + 1, g + m + 1, cmp);
    for (int i = 1; i <= n; ++i)
        fa[i] = i;

    for (int i = 1; i <= m; ++i) {
        Edge<type> e = g[i];
        // 判断是否连通
        if (find(e.from) != find(e.to)) {
            ans += g[i].dis;
            fa[find(e.from)] = find(e.to);
        }
        // 如果已经形成最小生成树了就退出
        if (++tot == edge - 1)
            break;
    }
    return ans;
}

例题