Prim算法

概述

最小生成树（Minimum Spanning Tree,MST）

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

其中，

$$w(T)=\sum_{(u,v)\in T}^{} w(u,v)$$

最小生成树其实是最小权重生成树的简称。我们称求取该生成树的问题成为最小生成树问题。一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言，对于非连通无向图来说，它的每一连通分量同样有最小生成树，它们的并被称为最小生成森林。

那么，我们如何来求最小生成树呢，由最小生成树的定义我们可以知道构建最小生成树是可以利用贪心算法去实现的，我们接下来介绍的算法也都是利用贪心算法去求得MST的。因为贪心算法的策略就是在每一步尽可能多的选择中选择最优的，在当前看是最好的选择，这种策略虽然一般不能在全局中寻找到最优解，但是对于最小生成树问题来说，它的确可以找到一颗权重最小的树。

算法简介

普里姆算法（Prim’s algorithm），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

算法思想

具体步骤

Prim算法是利用贪心算法实现的，我们确定根节点，从这个结点出发。普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。下面描述我们假设G=(V,E)是加权连通图，Vnew是G上最小生成树中点的集合，Enew是G上最小生成树中边的集合。

1. 输入：一个加权连通图，其中顶点集合为V，边集合为E；
2. 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3. 重复下列操作，直到Vnew = V：
   1. 在集合E中选取权值最小的边，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且$v \in V$（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
   2. 将v加入集合Vnew中，将边加入集合Enew中；
4. 输出：使用集合Vnew和Enew来描述所得到的最小生成树。

解释：对于3中的第一个步骤，用白话来说就是在Vnew之外选一个到Vnew距离最近的点（起点是Vnew中的任一点，终点是Vnew之外的点），Vnew就是逐步构建起来的最小生成树的点集；接下来的步骤就是将刚刚选出来的点和边纳入最小生成树

举例说明

设置2个数据结构：

• lowcost[i]：表示以i为终点的边到最小生成树的最小权值，当lowcost[i]=0说明以i为终点的边的最小权值=0，也就是表示i点加入了最小生成树
• mst[i]：表示对应lowcost[i]的起点，即说明边是最小生成树的一条边，规定当mst[i]=0表示起点i加入最小生成树

初始状态：

我们假设V1是起始点，进行初始化（*代表无限大，即无通路，所有点默认起始点为1）：

i	2	3	4	5	6
lowcost[i]	6	1	5	*	*
mst[i]	1	1	1	1	1

明显看出，以V3为终点的边的权值最小=1，所以边=1加入MST

此时，因为点V3的加入，需要更新lowcost数组和mst数组：

i	2	3	4	5	6
lowcost[i]	5	0	5	6	4
mst[i]	3	0	1	3	3

明显看出，以V6为终点的边的权值最小=4，所以边=4加入MST

此时，因为点V6的加入，需要更新lowcost数组和mst数组：

i	2	3	4	5	6
lowcost[i]	5	0	2	6	0
mst[i]	3	0	6	3	0

明显看出，以V4为终点的边的权值最小=2，所以边=4加入MST

此时，因为点V4的加入，需要更新lowcost数组和mst数组：

i	2	3	4	5	6
lowcost[i]	5	0	0	6	0
mst[i]	3	0	0	3	0

明显看出，以V2为终点的边的权值最小=5，所以边=5加入MST

此时，因为点V2的加入，需要更新lowcost数组和mst数组：

i	2	3	4	5	6
lowcost[i]	0	0	0	3	0
mst[i]	0	0	0	2	0

很明显，以V5为终点的边的权值最小=3，所以边=3加入MST

i	2	3	4	5	6
lowcost[i]	0	0	0	0	0
mst[i]	0	0	0	0	0

至此，MST构建成功，如图所示：

代码实现

输入格式

第一行包含两个整数 N,M，表示该图共有 N个结点和 M 条无向边。

接下来 M行每行包含三个整数 X、Y、Z，分别表示有一条长度为 Z的无向边连接结点 X，Y。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出orz

输入输出样例

输入1

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出1

7

输入2

5 5 
1 2 3
2 3 4
1 3 4
1 3 5
4 5 6

输出2

orz

邻接矩阵实现：

#include <iostream>
#include <cstring>
#include <climits>

using namespace std;

const int MAXN = 5001;
int n, m; // n个节点，m条边
int graph[MAXN][MAXN];
int lowcost[MAXN]; //表示以i为终点的边到最小生成树的最小权值
int mst[MAXN];     //表示对应lowcost[i]的起点

int prim()
{

    int sum = 0;
    //初始化lowcost和mst，选定第一个节点为起点
    for (int i = 2; i <= n; i++)
    {
        lowcost[i] = graph[1][i];
        mst[i] = 1;
    }
    mst[1] = 0;
    for (int i = 0; i < n - 1; i++)
    {
        int minn = INT_MAX, minId = 0;
        //寻找 到最小生成树距离最小的点
        for (int j = 2; j <= n; j++)
        {
            if (lowcost[j] < minn && lowcost[j] != 0)
            {
                minn = lowcost[j];
                minId = j;
            }
        }
        if (minn == INT_MAX)
            return 0;       //如果minn值没变，说明该图不连通
        sum += minn;        //累加权值
        lowcost[minId] = 0; //将minId表示的点纳入最小生成树
        //更新lowcost和mst数组
        for (int j = 2; j <= n; j++)
        {
            //由于最小生成树只比上一个状态多一个点，变化只是由这一个点引起的，遍历该点到其他点的边即可
            if (graph[minId][j] < lowcost[j])
            {
                lowcost[j] = graph[minId][j];
                mst[j] = minId;
            }
        }
    }
    return sum;
}

int main()
{
    cin >> n >> m;
    //初始化graph为极大值
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            graph[i][j] = INT_MAX;
    for (int i = 0; i < m; i++)
    {
        int from, to, cost;
        cin >> from >> to >> cost;
        graph[from][to] = cost;
        graph[to][from] = cost;
    }
    int res = prim();
    if (res == 0)
        cout << "orz" << endl;
    else
        cout << res << endl;
    return 0;
}

链表实现：

#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>

using namespace std;

const int MAXN = 5001; //最大点数
const int MAXM = 2e5;  //最大边数
int n, m;              // n个节点，m条边
int cnt;
int dis[MAXN];  //已经加入最小生成树的的点到没有加入的点的最短距离
int head[MAXN]; //节点i的所有连边
int vis[MAXN];  //标记点是否已经纳入最小生成树，1表示已纳入，0表示未纳入

struct Node
{
    int v, w, next;
} edge[MAXM << 1];

//链式前向星加边
void add(int u, int v, int w)
{
    edge[++cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

int prim()
{
    int sum = 0, tot = 0, minId = 1;
    memset(vis, 0, sizeof(vis)); //初始化为0
    //初始化dis，选定第一个节点为起点，初始化dis
    vis[1] = 1; //设置1号节点已纳入最小生成树
    for (int i = head[1]; i; i = edge[i].next)
        dis[edge[i].v] = min(dis[edge[i].v], edge[i].w); //用min防止重边

    while (++tot < n)
    {
        int minn = INT_MAX, minId = 0;
        //寻找 到最小生成树距离最小的点
        for (int i = 2; i <= n; i++)
        {
            if (!vis[i] && dis[i] < minn)
            {
                minn = dis[i];
                minId = i;
            }
        }
        if (minn == INT_MAX)
            return 0;   //如果minn值没变，说明该图不连通
        sum += minn;    //累加权值
        vis[minId] = 1; //将minId表示的点纳入最小生成树
        //枚举minId的所有连边，更新dis数组
        for (int i = head[minId]; i; i = edge[i].next)
        {
            int v = edge[i].v;
            if (dis[v] > edge[i].w && !vis[v])
                dis[v] = edge[i].w;
        }
    }
    return sum;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int from, to, cost;
        cin >> from >> to >> cost;
        add(from, to, cost);
        add(to, from, cost);
    }
    //初始化dis为极大值
    for (int i = 0; i <= n; i++)
        dis[i] = INT_MAX;
    int res = prim();
    if (res == 0)
        cout << "orz" << endl;
    else
        cout << res << endl;
    return 0;
}