通用算法-最小生成树（Prim）

一、环境

系统：win10
语言：python 3.7

二、原理说明

在图论中，对于连通图，生成一颗最小生成树，使得其所有点连通，并且权重最小，使用Prim算法，原理如下图所示：

GIF

描述：先随机设定一个起点，按照距离最近的原则将周围的点依次访问，并且加入到一块，访问的时候需要记录该节点的父节点。

原理相对简单，代码设计思路为：

假设选取了0点作为起始点，先对0可以连接的点的距离进行访问，inf表示连接不上（距离无穷大）

1 2	[-1,8,12,inf,inf,inf,inf,inf,inf] [ 0,0, 0, 0, 0, 0, 0, 0, 0] # 标记每个节点的父节点是谁

比较除0之外的其他数字（0可以理解为已经被访问过），选择最小值（这里是1号节点），然后将这个位置标记为-1。

1 2	[-1,-1,12,inf,inf,inf,inf,inf,inf] [ 0, 0, 0, 0, 0, 0, 0, 0, 0] # 标记每个节点的父节点是谁

将上一步选中的点（1号节点），计算与剩下点之间的距离，如果比上一步中得到的数字小，则保存进去，数组更新为：

1 2	[-1,-1,12,25,9,inf,inf,inf,inf] [ 0, 0, 0, 1, 1, 0, 0, 0, 0] # 标记每个节点的父节点是谁

比较除0之外的其他数字，选择最小值（这里是4号节点），将4设置为-1，表示已经访问过。

1 2	[-1,-1,12,25,-1,inf,inf,inf,inf] [ 0, 0, 0, 1, 1, 0, 0, 0, 0] # 标记每个节点的父节点是谁

同理，计算4号节点与剩下点之间的距离，如果比上一步中得到的数字小，则保存进去。如此循环往复。

1 2	[-1,-1,12,25,-1,inf,inf,inf,inf] [ 0, 0, 0, 1, 1, 0, 0, 0, 0] # 标记每个节点的父节点是谁

三、代码实现

参考别人用C实现的思路²，这里使用python代码对其进行复现：

根据上述图，设计图的邻阶矩阵¹
创建两个长度为n的数组，一个记录距离，一个记录父子关系。其中n为图的节点个数

代码实现如下：

import numpy as np

def GenerateGrap():
    """
    纯手工构建邻阶矩阵，其中np.inf表示无穷大
    :return:  邻阶矩阵
    """
    grap = []

    grap.append([0,          8,     12, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf])
    grap.append([0.1,         0,     13,     25,      9, np.inf, np.inf, np.inf, np.inf])
    grap.append([12,         13,      0,     14, np.inf, np.inf,     21, np.inf, np.inf])
    grap.append([np.inf,     25,     14,      0,     20,      8,     12,     12,     16])
    grap.append([np.inf,      9, np.inf,     20,      0,     19, np.inf, np.inf, np.inf])
    grap.append([np.inf, np.inf, np.inf,      8,     19,      0, np.inf,     11, np.inf])
    grap.append([np.inf, np.inf,     21,     12, np.inf, np.inf,      0, np.inf,     11])
    grap.append([np.inf, np.inf, np.inf,     12, np.inf,     11, np.inf,      0,      9])
    grap.append([np.inf, np.inf, np.inf,     16, np.inf, np.inf,     11,      9,      0])

    return np.array(grap)

def getMinIndex(arr):
    temp = np.copy(arr)
    temp[temp[:] == -1] = np.inf

    return np.argmin(temp)

def Prim(grap):
    col,row = grap.shape

    lowCost = np.zeros(col)
    parentTable = np.zeros(col)

    grap[grap[:] == 0] = np.inf

    start = 0
    for i in range(col):
        lowCost[i] = grap[start][i]
    lowCost[start] = -1  #访问过的节点设置为-1

    for i in range(0,col):
        k = getMinIndex(lowCost)   # 返回最小值下标
        start = k
        lowCost[start] = -1

        for j in range(0,col):
            if grap[start][j] < lowCost[j] and lowCost[j] != -1:
                lowCost[j] = grap[start][j]
                parentTable[j] = start  #记录当前最小距离的父节点是谁

    return parentTable

grap = GenerateGrap()
print(Prim(grap))

输出结果：

1	[0. 0. 0. 2. 1. 3. 8. 5. 7.]

参考文献

¹. 邻接矩阵 - 无向图 ↩

². 最小生成树-Prim算法和Kruskal算法 ↩