199-Prim算法（1）.md

一：背景

假设要在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步	8	3	2	+∞	{ 3 }
第2步	3	3	×	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→1比low_cost[1]小，故更新low_cost[1]为3；3与2邻接，因3→2比low_cost[2]大，故不更新low_cost[2] ；3与4邻接，因3→4比low_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→4比low_cost[4]小，故更新low_cost[4]为1。在low_cost[]中找到最小值，其顶点为4，即此时又找到一条边：2→4。

第5步：最小生成树完成，停止。

三：代码

/**
 *
 * author : 刘毅（Limer）
 * date   : 2017-05-29
 * mode   : C++
 */

#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;
}

运行截图：

四：算法的正确性证明

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

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)$