python

12 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 858. 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≤10^5, 图中涉及边的边权的绝对值均不超过 10000。

输入样例：

输出样例：

二、解题思路

最小生成树

最小生成树一般是说的无向图，有向图的最小生成树一般不会用到。
连通图：在无向图中，若任意两个顶点v_i与v_j都有路径相通，则称该无向图为连通图。
连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。一个无向图可以有多个最小生成树，但最小生成树的边权和一定是最小的。

实际的场景：比如N个城市，需要根据实际情况建高铁，我们知道这些城市之间有些是相通的，距离也知道，有些城市之间是不通的，也不打算建高铁。那么，我们如何能知道怎么建设高铁的路线使用城市之间全能连通，并且路线和最小呢？因为这样才省钱，还能保证所有城市联通啊！

三、`Prim`算法

和dijkstra非常相似,dijkstra算法是计算到顶点的距离，而Prim算法是计算到集合的距离，下面详细讲解：

比如本题:稠密图，节点个数500,边数10^5,好多的边啊，所以需要定义g[N][N], 500*500=250000 > 10^5 。

prim 算法采用的是一种贪心的策略,每次将离连通部分的最近的点和点对应的边加入的连通部分，连通部分逐渐扩大，最后将整个图连通起来，并且边长之和最小。

算法步骤

把所有距离dis[N]初始化为INF。
用一个 pre 数组保存节点的前驱节点是谁。pre[i] = k 表示节点 i 和节点 k 之间需要有一条边。初始时，pre 的各个元素置为 -1。
循环n次，将所有点准备加入到集合中。
- 找出不在集合中的(!st[j])距离集合最近的点dis[j]，如果是有多个距离一样近，那么选择号小的那个,命名为t。
- 累加最小权值
- 利用t更新未加入集合中的其它各点到集合的最短距离
- 将t加入到集合中

模拟流程

我们将图中各个节点用数字 1 \sim n 编号。

要将所有景点连通起来，并且边长之和最小，步骤如下：用一个 st 数组表示节点是否已经连通。st[i] 为真，表示已经连通，st[i] 为假，表示还没有连通。初始时，st 各个元素为假。即所有点还没有连通。用一个 dis 数组保存各个点到连通部分的最短距离，dis[i] 表示 i 节点到连通部分的最短距离。初始时，dis 数组的各个元素为无穷大。用一个 pre 数组保存节点的是和谁连通的。pre[i] = k 表示节点 i 和节点 k 之间需要有一条边。初始时，pre 的各个元素置为 -1。
从 1 号节点开始扩充连通的部分，【之所以从一号结点开始，是因为大家都是距离集合正无穷，那么号小的优先！】，所以 1 号节点与连通部分的最短距离为 0，即dis[i] 值为 0。
遍历 dis 数组，找到一个还没有连通起来，但是距离连通部分最近的点，假设该节点的编号是 t。t节点就是下一个应该加入连通部分的节点，st[t] 置为 true。用青色点表示还没有连通起来的点，红色点表示连通起来的点。这里青色点中距离最小的是 dis[1]，因此 st[1] 置为 true。

4.遍历所有与 t 相连但没有加入到连通部分的点 j，如果 j 距离连通部分的距离大于 t \sim j 之间的距离，即 dis[j] > g[t][j]（g[t][j] 为 t \sim j 节点之间的距离），则更新 dis[j] 为 g[t][j]。这时候表示，j 到连通部分的最短方式是和 t 相连，因此，更新pre[j] = t。

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

重复 3, 4步骤，直到所有节点的状态都被置为 1. 这里青色点中距离最小的是 dis[2]，因此 st[2] 置为 1。

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

选dis[4]，更新dis[3]，dis[5]，pre[3]，pre[5]。选dis[5]，没有可更新的。选dis[3]，没有可更新的。

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

经验总结

最小生成树并不唯一，但它的边权最小值是唯一的。所以，一般没有要求求出最小生成树长成什么样子，而是要求输出最小生成树的边权最小值。
因为Prim算法需要反复的求每两个点之间的距离，这就决定了 邻接矩阵更合适，因为相对于邻接表，邻接矩阵可以快速提供两个点之间的距离，而邻接表是链表，想要获取两个点之间的距离就没那么方便。
边数较少可以用Kruskal,因为Kruskal算法每次查找最短的边。边数较多可以用Prim，因为它是每次加一个顶点，对边数多的适用。

四、朴素版`Prim`算法代码

#include <bits/stdc++.h>

using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;

int n, m;
int g[N][N]; // 稠密图，邻接矩阵
int dis[N];  // 这个点到集合的距离
bool st[N];  // 是不是已经使用过
int res;     // 最小生成树里面边的长度之和

// 普利姆算法求最小生成树
int prim() {
    // 距离初始化无穷大,表示所有结点都在生成树之外
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;

    for (int i = 0; i < n; i++) { // 迭代n次
        /*
        1、找到集合外，距离集合最近的点，记为t,此时有两种情况进行猴子选大王：
        （1）首次查找,此时还没有大王，那么，默认第一个找到的就是大王
        （2）非首次查找,那么PK距离最小的成为大王
        */
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dis[t] > dis[j])) t = j;

        /*2、如果不是第一个点，并且剩余的点距离集合的最小距离是INF，说明现在没有点可以连通到生成树，
         这时不是连通图，没有最小生成树，返回INF

        如果是第一个点，因为把它加到集合中去的代码是在下面进行的，此时它也没有被加入到集合中去，所以dist[t]=INF,这时不能说无解
        因为才刚刚开始，需要特判一下
        */
        if (i && dis[t] == INF) return INF;

        // 3、同上，这里也需要特判一下是不是第1个节点，第一个节点不用加边权值，其它的需要加
        if (i) res += dis[t];

        // 4、因为本轮选择的是结点t,那么用t更新其它未加入到集合中点到集合的距离
        for (int j = 1; j <= n; j++)
            if (!st[j] && dis[j] > g[t][j])
                dis[j] = g[t][j];

        // 5、把t放到集合中
        st[t] = true;
    }
    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; // 否则输出t

    return 0;
}

五、带路径输出的`Prim`算法

#include <bits/stdc++.h>

using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;

int n, m;
int g[N][N]; // 稠密图，邻接矩阵
int dis[N];  // 这个点到集合的距离
bool st[N];  // 是不是已经使用过
int res;     // 最小生成树里面边的长度之和
int pre[N];  // 前驱结点

// 普利姆算法求最小生成树
int prim() {
    memset(dis, 0x3f, sizeof dis);
    memset(pre, -1, sizeof pre); // 记录前驱路径
    dis[1] = 0;

    for (int i = 0; i < n; i++) { // 迭代n次
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dis[t] > dis[j])) t = j;
        if (i && dis[t] == INF) return INF; // 非连通图，没有最小生成树
        if (i) res += dis[t];
        for (int j = 1; j <= n; j++)
            if (!st[j] && g[t][j] < dis[j]) {
                dis[j] = g[t][j];
                pre[j] = t; // 记录是由谁转移而来
            }
        st[t] = true;
    }
    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;

    // 输出前驱结点
    for (int i = 1; i <= n; i++) printf("%d ", pre[i]);
    return 0;
}

12 KiB Raw Permalink Blame History Unescape Escape