最小生成树——普里姆算法（prim)

生成树就是在保证自身是树（不存在环）的前提下，拥有尽可能多的边，它拥有G的所有顶点。

最小生成树就是指，各边权值总和最小的生成树。

举个例子，下面左边这个加权图的最小生成树就如右图所示

普里姆算法

1、设图G = (V,E)所有顶点的集合为V，最小生成树中顶点的集合为T。

2、循环执行下述处理直至T=V

• 在连接T内顶点与V-T内顶点的边中选取权值最小的边，并将其作为最小生成树的边，将u添加到最小生成树里面。

实现普里姆算法的关键在于如何保存权值最小的边。

对于题目ALDS1_12_A:

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/12/ALDS1_12_A

题目给出的是邻接矩阵表示法表示的无向图.

对于无向加权图，普里姆算法的处理过程如下图所示：

我们在具体的代码实现中，对于邻接矩阵表示法，应该把不存在的边的值设置为无穷大，那么我们就可以比较方便地实现代码。

具体代码如下：

#include <iostream>
#include <string.h>
using namespace std;

const int maxn = 105;
const int inf = (1 << 21);
const int white = 0;
const int gray = 1;
const int black = 2;

int n, G[maxn][maxn] = {-1};

int prim()
{
    int u, minv;                       //u是当前结点编号，minv是当前的最小权值
    int d[maxn], p[maxn], color[maxn]; //d[n]是顶点n与父节点的边的权值最小的边的权值。p是上述顶点的父节点，color表示访问状态
    memset(p, -1, sizeof(p));

    for (int i = 0; i < n; ++i)
        d[i] = inf;

    memset(color, white, sizeof(color));

    d[0] = 0;

    while (true)
    {
        minv = inf;
        u = -1;
        for (int i = 0; i < n; ++i)//找到当前与生成树相连的边中，权值最小的。然后把u点切换过去。
        {
            if (color[i] != black && minv > d[i])
            {
                u = i;
                minv = d[i];
            }
        }

        if (u == -1)
            break; //最小生成树已经建立完全

        color[u] = black;
        for (int v = 0; v < n; ++v) //更新与当前节点u相连的节点v的d
        {
            if (color[v] != black && G[u][v] != inf)
            {
                if (d[v] > G[u][v])
                {
                    d[v] = G[u][v];
                    p[v] = u;
                    color[v] = gray;
                }
            }
        }
    }

    int sum = 0;
    for (int i = 0; i < n; ++i)
    {
        if (p[i] != -1)
        {
            sum += G[i][p[i]];
        }
    }

    return sum;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> G[i][j];
            if (G[i][j] == -1)
                G[i][j] = inf;
        }
    }

    cout << prim() << endl;
}

考察

在使用邻接矩阵实现的普里姆算法中，我们需要遍历图的所有顶点来确定最小的顶点u，且整个算法的遍历次数与顶点数相等，因此算法复杂度为O(n²).

ps：如果使用二叉堆（优先级队列）来选定顶点，那么普里姆算法的效率将大大提高。

转载本文请注明出处：https://www.longjin666.top/?p=744

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~