MENU

最小生成树(1):Prim算法

May 28, 2018 • 文章

一:背景

假设要在n个城市之间通信联络网,则连通n个城市只需要n-1条线路。这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网。

上面的这个问题,就是最小生成树的问题。这篇文章就来介绍下解决这一问题的Prim算法(普里姆算法),该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现,并在1957年由美国计算机科学家罗伯特·普里姆独立发现,1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。

二:算法过程

我们用一个例子来具体说明普里姆算法的流程。

随机选一起点,假如为0,low_cost[i]表示以i为终点的边的权值。其过程描述如下:

步骤low_cost[1]low_cost[2]low_cost[3]low_cost[4]已找到的集合
第1步832+∞{ 3 }
第2步33×5{ 3, 1 }
第3步×3×5{ 3, 1, 2 }
第4步×××1{ 3, 1, 2, 4 }
第5步××××{ 3, 1, 2, 4 }

第1步:从起点0开始,找到与其邻接的点:1,2,3,更新low_cost[]数组,因0不与4邻接,故low_cost[4]为正无穷。在low_cost[]中找到最小值,其顶点为3,即此时已找到最小生成树中的一条边:0→3

第2步:从3开始,继续更新low_cost[]数组:3与1邻接,因3→1low_cost[1]小,故更新low_cost[1]为3;3与2邻接,因3→2low_cost[2]大,故不更新low_cost[2] ;3与4邻接,因3→4low_cost[4]小,故更新low_cost[4]为5。在low_cost[]中找到最小值,其顶点为1或者2,随便取一个即可,我们这里取1。即此时又找到一条边:3→1

第3步:从1开始,继续更新low_cost[]数组:因与1邻接的点都被放入最小生成树中,故不更新,直接在low_cost[]中找到最小值,其顶点为2,即此时又找到一条边:0→2

第4步:从2开始,继续更新low_cost[]数组:2与4邻接,因2→4low_cost[4]小,故更新low_cost[4]为1。在low_cost[]中找到最小值,其顶点为4,即此时又找到一条边:2→4

第5步:最小生成树完成,停止。

三:代码

#include <iostream>

using namespace std;

int  matrix[100][100]; // 邻接矩阵
bool visited[100];     // 标记数组
int  low_cost[100];    // 边的权值
int  path[100];        // 记录生成树的路径
int  source;           // 指定生成树的起点
int  vertex_num;       // 顶点数
int  edge_num;         // 边数
int  sum;              // 生成树权和

void Prim(int source)
{
    memset(visited, 0, sizeof(visited));
    visited[source] = true;
    for (int i = 0; i < vertex_num; i++)
    {
        low_cost[i] = matrix[source][i];
        path[i] = source;
    }

    int min_cost;       // 权值最小
    int min_cost_index; // 权值最小的下标
    sum = 0;
    for (int i = 1; i < vertex_num; i++) // 除去起点,还需要找到另外 vertex_num-1 个点
    {
        min_cost = INT_MAX;
        for (int j = 0; j < vertex_num; j++)
        {
            if (visited[j] == false && low_cost[j] < min_cost) // 找到权值最小
            {
                min_cost = low_cost[j];
                min_cost_index = j;
            }
        }

        visited[min_cost_index] = true;  // 该点已找到,进行标记
        sum += low_cost[min_cost_index]; // 更新生成树权和

        for (int j = 0; j < vertex_num; j++) // 从找到的最小下标更新 low_cost 数组
        {
            if (visited[j] == false && matrix[min_cost_index][j] < low_cost[j])
            {
                low_cost[j] = matrix[min_cost_index][j];
                path[j] = min_cost_index;
            }
        }
    }
}

int main()
{
    cout << "请输入图的顶点数(<=100):";
    cin >> vertex_num;
    cout << "请输入图的边数:";
    cin >> edge_num;

    for (int i = 0; i < vertex_num; i++)
        for (int j = 0; j < vertex_num; j++)
            matrix[i][j] = INT_MAX; // 初始化 matrix 数组

    cout << "请输入边的信息:\n";
    int u, v, w;
    for (int i = 0; i < edge_num; i++)
    {
        cin >> u >> v >> w;
        matrix[u][v] = matrix[v][u] = w;
    }

    cout << "请输入起点(<" << vertex_num << "):";
    cin >> source;
    Prim(source);

    cout << "最小生成树权和为:" << sum << endl;
    cout << "最小生成树路径为:\n";
    for (int i = 0; i < vertex_num; i++)
        if (i != source)
            cout << i << "----" << path[i] << endl;

    return 0;
}

运行如下:

请输入图的顶点数(<=100):5
请输入图的边数:7
请输入边的信息:
0 1 8
0 2 3
0 3 2
1 3 3
3 2 4
2 4 1
3 4 5
请输入起点(<5):0
最小生成树权和为:9
最小生成树路径为:
1----3
2----0
3----0
4----2

四:算法的正确性证明

以下除非特别说明,否则都默认是连通图,即是存在最小生成树的。

Prim算法利用了最小生成树(Minimu Spanning Tree,简称MST)性质,描述为:

假设$N=(V,\{E\})$是一个连通图($V$为顶点集合,$\{E\}$为边集合),$U$是已被加入生成树的顶点集合。若$(u,v)$是一条具有最小权值的边,其中$u∈U,v∈V-U$ (其中$V-U$就是未被加入生成树的顶点集合,如下图),则必存在一棵包含边$(u,v)$的最小生成树。

可以用反证法证明。见下图,假设图$N$的任何一棵最小生成树都不包含$(u,v)$。设$T$是$N$上的一棵最小生成树,当将边$(u,v)$加入到$T$时,由生成树的定义,$T$中必存在一条包含$(u,v)$的回路。另一方面,由于$T$是生成树,则在$T$上必存在另一条边$(u',v')$,其中$u'∈U,v'∈V-U$,且$u$与$u'$,$v$与$v'$之间均有路径相通。删去边$(u',v')$,便可消除上述回路,同时得到另一棵生成树$T'$。因为$(u,v)$的权值不大于$(u',v')$,故$T'$的权值和不大于$T$,$T'$是包含$(u,v)$的一棵最新小生成树。和假设矛盾。

上述所说的$(u',v')$即为$u→y→z→v$中的某条边。

对于初学者来说,把上述的MST性质和Prim算法联系起来还是有点困难的。读者可以这样去理解,Prim本质上就是利用了贪心思想,随机选取一顶点作为起点,加入到集合$U$,接着找到与其关联的最小权值的边,该边上的另一个点也加入到$U$,接着再从$U$中的两个点出发继续向外找最小权值的边,找到后再加入第三个点,就这样重复下去。因为每次都是找最小值,所以当所有点都被加入$U$时,最小生成树也就被确定了。

五:时间复杂度

Prim算法和Dijkstra 算法的时间复杂度一样,读者可以点击查看,所以这里就不详细陈述了,附上一张表即可,其中$m$为边数,$n$为顶点数。

最小边,权的数据结构时间复杂度
邻接矩阵,搜索(即本程序所用)$O(n^2)$
二叉堆,邻接表$O((m+n)logn)$
斐波那契堆,邻接表$O(m+nlogn)$
Archives QR Code Tip
QR Code for this page
Tipping QR Code