文章目录

一、最小生成树简介

二、Prim 算法实现最小生成树

1. Prim 算法

2. Prim 算法具体实现详见例题 Prim 算法求最小生成树。

三、Kruskal 算法实现最小生成树

1. Kruskal 算法思路

2. Kruskal 算法实现过程

3. Kruskal 算法具体实现详见例题 Kruskal 算法求最小生成树。

四、Prim 算法例题——Prim 算法求最小生成树

五、Kruskal 算法例题——Kruskal 算法求最小生成树

一、最小生成树简介

最小生成树是指一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。

在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集且为无循环图，使得联通所有结点的的 w(T) 最小，则此 T 为 G 的最小生成树。

最小生成树是最小权重生成树的简称，可以用 Kruskal（克鲁斯卡尔）算法或 Prim（普里姆）算法求出。

这里需要注意的是：

（1） 最小生成树可能有多个，但边的权值之和总是唯一且最小的。

（2） 最小生成树的边数 = 定点数 - 1，砍掉一条则不连通，增加一条则会出现回路。

（3） 若一个连通图本身就是一颗树，则其最小生成树就是它本身。

（4） 只有连通图才有生成树，非连通图只有生成森林

二、Prim 算法实现最小生成树

1. Prim 算法

• Prim 算法采用的是一种贪心的策略。
• 每次将离连通部分的最近的点和点对应的边加入的连通部分，连通部分逐渐扩大，最后将整个图连通起来，并且边长之和最小。
• 我们将图中各个节点用数字 1 ~ n 编号。
• 

要将所有景点连通起来，并且边长之和最小，步骤如下：

（1） 用一个 state 数组表示节点是否已经连通。state[i] 为真，表示已经连通，state[i] 为假，表示还没有连通。初始时，state 各个元素为假。即所有点还没有连通。

用一个 dist 数组保存各个点到连通部分的最短距离，dist[i] 表示 i 节点到连通部分的最短距离。初始时，dist 数组的各个元素为无穷大。

用一个 pre 数组保存节点的是和谁连通的。pre[i] = k 表示节点 i 和节点 k 之间需要有一条边。初始时，pre 的各个元素置为 -1。

（2） 从 1 号节点开始扩充连通的部分，所以 1 号节点与连通部分的最短距离为 0，即 disti[1] 置为 0。

（3） 遍历 dist 数组，找到一个还没有连通起来，但是距离连通部分最近的点，假设该节点的编号是 i。i 节点就是下一个应该加入连通部分的节点，stata[i] 置为 1。

用青色点表示还没有连通起来的点，红色点表示连通起来的点。

这里青色点中距离最小的是 dist[1]，因此 state[1] 置为 1。

（4）遍历所有与 i 相连但没有加入到连通部分的点 j，如果 j 距离连通部分的距离大于 i j 之间的距离，即 dist[j] > w[i][j]（w[i][j] 为 i，j 节点之间的距离），则更新 dist[j] 为 w[i][j]。

这时候表示，j 到连通部分的最短方式是和 i 相连，因此，更新 pre[j] = i。

与节点 1 相连的有 2， 3， 4 号节点。1->2 的距离为 100，小于 dist[2]，dist[2] 更新为 100，pre[2] 更新为1。1->4 的距离为 140，小于 dist[4]，dist[4] 更新为 140，pre[2] 更新为1。1->3 的距离为 150，小于 dist[3]，dist[3] 更新为 150，pre[3] 更新为1。

• （5）重复 3，4 步骤，直到所有节点的状态都被置为 1。
• 这里青色点中距离最小的是 dist[2]，因此 state[2] 置为 1

与节点 2 相连的有 5， 4 号节点。2->5 的距离为 80，小于 dist[5]，dist[5] 更新为 80，pre[5] 更新为 2。2->4 的距离为 80，小于 dist[4]，dist[4] 更新为 80，pre[4] 更新为 2。

• 选 dist[4]，更新 dist[3]，dist[5]，pre[3]，pre[5]。

选 dist[5]，没有可更新的。

选 dist[3]，没有可更新的。

此时 dist 数组中保存了各个节点需要修的路长，加起来就是。pre 数组中保存了需要选择的边。

2. Prim 算法具体实现详见例题 Prim 算法求最小生成树。

三、Kruskal 算法实现最小生成树

1. Kruskal 算法思路

将所有边按照权值的大小进行升序排序，然后从小到大一一判断。

如果这个边与之前选择的所有边不会组成回路，就选择这条边分；反之，舍去。

直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。

筛选出来的边和所有的顶点构成此连通网的最小生成树。

判断是否会产生回路的方法为：使用并查集。

在初始状态下给各个个顶点在不同的集合中。

遍历过程的每条边，判断这两个顶点的是否在一个集合中。

如果边上的这两个顶点在一个集合中，说明两个顶点已经连通，这条边不要。如果不在一个集合中，则要这条边。

2. Kruskal 算法实现过程

举个例子，下图一个连通网，Kruskal 算法查找图 1 对应的最小生成树，需要经历以下几个步骤：

• 将连通网中的所有边按照权值大小做升序排序：

从 B-D 边开始挑选，由于尚未选择任何边组成最小生成树，且 B-D 自身不会构成环路，所以 B-D 边可以组成最小生成树。

• D-T 边不会和已选 B-D 边构成环路，可以组成最小生成树：

• A-C 边不会和已选 B-D、D-T 边构成环路，可以组成最小生成树：

• C-D 边不会和已选 A-C、B-D、D-T 边构成环路，可以组成最小生成树：

C-B 边会和已选 C-D、B-D 边构成环路，因此不能组成最小生成树：

B-T 、A-B、S-A 三条边都会和已选 A-C、C-D、B-D、D-T 构成环路，都不能组成最小生成树。而 S-A 不会和已选边构成环路，可以组成最小生成树

如图下图 所示，对于一个包含 6 个顶点的连通网，我们已经选择了 5 条边，这些边组成的生成树就是最小生成树。

3. Kruskal 算法具体实现详见例题 Kruskal 算法求最小生成树。

四、Prim 算法例题——Prim 算法求最小生成树

题目描述

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图 G = (V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n = |V|，m = |E|。

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

数据范围

1 ≤ n ≤ 500

1 ≤ m ≤ 1e5

图中涉及边的边权的绝对值均不超过 10000。

输入样例

4 5

1 2 1

1 3 2

1 4 3

2 3 2

3 4 4

输出样例

6

实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
//dist[N]表示边长
int dist[N];
//st[N]表示是否使用过
bool st[N];
int prim()
{
    memset(dist, 0x3f, sizeof dist);
    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 (i && dist[t] == INF)
        {
            return INF;
        }
        if (i)
        {
            res += dist[t];
        }
        st[t] = true;
        for (int j = 1; j <= n; j ++ )
        {
            dist[j] = min(dist[j], g[t][j]);
        }
    }
    return res;
}
int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        //可能会有重边，取最小值
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    int t = prim();
    if (t == INF) 
    {
        puts("impossible");
    }
    else
    {
        cout << t << endl;
    }
    return 0;
}

五、Kruskal 算法例题——Kruskal 算法求最小生成树

题目描述

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图 G = (V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n = |V|，m = |E|。

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

数据范围

1 ≤ n ≤ 1e5

1 ≤ m ≤ 2∗1e5

图中涉及边的边权的绝对值均不超过 1000。

输入样例

4 5

1 2 1

1 3 2

1 4 3

2 3 2

3 4 4

输出样例

6

实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 200010, INF = 0x3f3f3f3f;
int n, m;
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];
}
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 = find(a), b = find(b);
        if (a != b)
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }
    if (cnt < n - 1)
    {
        return INF;
    }
    return res;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    int t = kruskal();
    if (t == INF)
    {
        puts("impossible");
    }
    else 
    {
        cout << t << endl;
    }
    return 0;
}