java、python实现啊哈算法 —— chapter8 最小生成树的 Prim算法

java、python实现啊哈算法 —— chapter8 最小生成树的 Prim算法

这一算法的核心其实就是Dijkstra算法，这也是上一篇文章写Dijkstra的原因。但是有一点不同：Dijkstra是单源最短路径，即每个点到原点的最短路径。

Prim算法的核心是每一个点到最小生成树的最短路径。下面上代码

Java版：

import java.util.Arrays;

public class PrimBasic {
    //初始化最大值
    static double max = Double.POSITIVE_INFINITY;
    //初始化一个邻接矩阵
    static double[][] map= new double[][]{
            {0, 1, 2, max, max, max},
            {1, 0, 6, 11, max, max},
            {2, 6, 0, 9, 13, max},
            {max, 11, 9, 0, 7, 3},
            {max, max, 13, 7, 0, 4},
            {max, max, max, 3, 4, 0}
    };
    static int n = map.length;
    //初始化距离矩阵,记录点到 生成树 的最短距离
    static double[] dis = map[0];
    //初始化一个标记数组，记录哪些点被确定
    static int[] book = new int[n];
    static void primBasic(int startPoint) {
        //将起始点在book数组中标记
        book[startPoint] = 1;
        //初始化一个计数变量
        int count = 1;
        //初始化一个变量，存储最小生成树中所有边的权值之和
        while (count != n) {
            //初始化一个最小值变量，存储点到 生成树 的最小权值
            double min = 999;
            //初始化一个变量，存储dis距离数组中最小值的下标
            int u = -1;
            //找到dis距离数组中权值最小的点，将这点确定下来
            for (int i = 0; i < n; i++) {
                if (dis[i] < min && book[i] == 0) {
                    min = dis[i];
                    u = i;
                }
            }
            book[u] = 1;
            count ++;
            //更新这一确定点的出边能到达的点 在dis中的权值
            for (int j = 0; j < n; j++) {
                if (dis[j] > map[u][j] && book[j] == 0) {
                    dis[j] = map[u][j];
                }
            }
        }
        return;
    }

    public static void main(String[] args) {
        primBasic(0);
        System.out.println(Arrays.toString(dis));
        int sum = 0;
        for (int i = 0; i < dis.length; i++) {
            sum += dis[i];
        }
        System.out.println(sum);
    }
}

python版：

import numpy as np

#声明一个邻接矩阵，表示各个点及点之间的权值
global e
#声明一个距离列表，存储各个点到生成树的距离
global dis
#声明一个book列表，用来标记哪些点在生成树中
global book

def prim(startpoint):
    # 初始化一个计数变量count，存储生成树中节点的个数，当所有节点都存入生成树中之后，退出方法
    count = 0
    #将起始点放入生成树中，作为生成树的根节点
    book[startpoint] = 1
    n = len(e)
    while count != n:
        #定义一个变量存储每个点在dis列表中的权值，从而帮助找到生成树之外的点中权值最小的点
        #这一点一定要在while循环内部定义，才能保证每趟循环能顺利找出最小值点
        min = 999
        #定义一个变量存储生成树外权值最小的点的下标,同样也要在while循环内部定义
        u = -1
        for i in range(n):
            if dis[i] < min and book[i] == 0:
                #循环比较，找出生成树外权值最小的点
                min = dis[i]
                u = i
        #将这一点加入到生成树中，并在book列表中标记
        count += 1
        book[u] = 1
        #循环遍历生成树外的点，找到距离新加入生成树的点最近的点，也就是距离生成树最近的点
        for j in range(n):
            if dis[j] > e[u][j] and book[j] == 0:
                dis[j] = e[u][j]
        #上面这步循环遍历就把dis列表中所有点的权值更新了，while的下一轮循环将会从dis列表中生成树之外的点中
        #找到权值最小的点加入到生成树中
    #while循环结束后，生成树中已经包含了所有的节点，退出方法
    return

if __name__ == '__main__':
    max = float('inf')
    e = [
            [0, 1, 2, max, max, max],
            [1, 0, 6, 11, max, max],
            [2, 6, 0, 9, 13, max],
            [max, 11, 9, 0, 7, 3],
            [max, max, 13, 7, 0, 4],
            [max, max, max, 3, 4, 0]
    ]
    dis = e[0]
    book = np.zeros((len(e),), dtype='int')
    prim(0)
    print(dis)
    sum = 0
    for num in dis:
        sum += num
    print(sum)

正确输出为19