prim算法

算法背景

计算稠密图的最小生成树最早是由罗伯特·普里姆在1957年发明的[1]，即Prim算法。之后艾兹赫尔·戴克斯特拉也独自发明了它[2]。但该算法的基本思想是由沃伊捷赫·亚尔尼克于1930年发明的[3]。所以该算法有时候也被称为Jarník算法或者Prim-Jarník算法。20世纪70年代，优先队列发明之后很快被用在了寻找稀疏图中的最小生成树上。1984年，迈克尔·弗里德曼和罗伯特·塔扬发明了斐波那契堆，Prim算法所需要的运行时间在理论上由${\displaystyle E\log E}$提升到了${\displaystyle E+V\log V}$。约瑟夫·克鲁斯卡尔在1956年发表了他的算法，在他的论文中提到了Prim算法的一个变种，而奥塔卡尔·布卢瓦卡在20世纪20年代的论文中就已经提到了该变种。M.Sollin在1961年重新发现了该算法，该算法后成为实现较好渐进性能的最小生成树算法和并行最小生成树算法的基础1。

以下各算法介绍中，${\displaystyle E}$表示图的边数，${\displaystyle V}$表示图的顶点数。　

算法分析

首先我们明白，图的算法背后都有实际的经济效益，它对我们现在的交通出行和工程起了很大的作用。

Prim算法是最小生成树的算法,我们还有一个最小生成树的算法是Kruskal算法,这两种算法的过程非常简单,prim有点贪心的味道,而kruskal则有点并查集的味道.

接下来我们开始一步一步分析算法:

首先我们要记住关键步骤,然后再开始处理细节:

抽象的方法利于我们分析问题

  1. 创建一个空集合
  2. 集合加入一个点
  3. 更新集合外的点到集合的距离

如此迭代所有的点,把这些点都加入集合里,每次都选离集合最近距离的点,这样我们就构建了一课最小生成树.

还有一些细节值得让我们注意,每次迭代怎么选取离集合最近的点呢

下面请看图解

dist指离集合最短距离,每次集合加入新的点要更新dist.初始化全为$\infty$.

因为在算法里int类型的范围大约是 $2*10^9$ 所以我们用 0x3f3f3f3f代替$\infty$.

visited 指点是否在集合里,在true,没在则false.

Step1

1

ps:广场到家的距离应该是5,公司到家的是3

D\V 广场 学校 机场 公司 家 公园
dist $+\infty$ $+\infty$ $+\infty$ $+\infty$ $+\infty$ $+\infty$
visited false false false false false false

Step2

image-20210823112353770

D\V 广场 学校 机场 公司 家 公园
dist 0 3 4 2 5 $+\infty$
visited true false false false false false

Step3

image-20210823112906907

D\V 广场 学校 机场 公司 家 公园
dist 0 3 4 0 3 $+\infty$
visited true false false true false false

Step3

image-20210823113827983

D\V 广场 学校 机场 公司 家 公园
dist 0 0 4 0 3 6
visited true true false true false false

Step4

image-20210823114317299

D\V 广场 学校 机场 公司 家 公园
dist 0 0 4 0 0 4
visited true true false true true false

Step5

image-20210823114653906

D\V 广场 学校 机场 公司 家 公园
dist 0 0 0 0 0 4
visited true true true true true false

Step6

image-20210823114900462

D\V 广场 学校 机场 公司 家 公园
dist 0 0 0 0 0 0
visited true true true true true true

最后所有点都已经加入集合里,最小生成树就构造出来了.计算每条边的总和就是最后的result.

\[\begin{align} result &= 3+4+2+3+4 \\ &= 16 \end{align}\]

代码实现2

#include <bits/stdc++.h>

using namespace std;

const int N = 510, M = 100010, INF = 0x3f3f3f3f;
int n, m;
int g[N][N], dist[N];
bool st[N]; // 是否在集合里

int prim()
{
    memset(dist, 0x3f, sizeof dist); // 初始dist都为∞
    dist[1] = 0; // 从第一个点开始依次加入集合;原点距离为0.
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        // 遍历没加入集合的点找最短dist
        for (int j = 1; j <= n; j++)
        {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        // 这时候就找到了离集合最近的点
        // 接下来，开始加入集合并更新在集合外所有点离集合最近的距离
        if (dist[t] == INF) return INF; // 不可到达 无法生成最小生成树
        st[t] = true; // 加入集合
        res += dist[t];
        // 开始更新
        for (int j = 1; j <= n; j++)
        {
            dist[j] = min(dist[j], g[t][j]);
        }

    }
    return res;

}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);
    while (m--)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        g[a][b] = g[b][a] = min(g[a][b], w);
    }

    int res = prim();
    if (res == INF) puts("impossible");
    else printf("%d\n", res);
    return 0;
}

  1. 最小生成树 - 维基百科，自由的百科全书 (ahut.cf) ↩

  2. 858. Prim算法求最小生成树 - AcWing题库 ↩