Prim算法:如何快速求解最小生成树?

2023-12-28 14:09:08

一、普里姆(Prim)算法概述

Prim算法是图论中的一种算法,可在加权连通图里搜索最小生成树。

最小生成树,简称MST。是给定一个带权的无向联通图,如何选取一颗生成树,使树上所有边权的总和为最小,这个树就叫最小生成树。最小生成树有以下特点:

  1. N个顶点,一定有N-1条边
  2. 包含全部顶点
  3. N-1条边都在图中

image-20231227205103160

这个算法的常见用途就是在包含n个顶点的连通图中,找出只有(n - 1)条边包含所有n个顶点的连通子图,也就是最小生成树。


二、普里姆(Prim)算法的基本思路

Prim算法的思路如下:

  1. 设G=(V,E)是连通网,T=(U,D)是最小生成树,V,U是顶点集合,E,D是边集合。
  2. 若从顶点u开始构造最小生成树,则从集合V中取出顶点u放进集合U中,并标记顶点v的visted[u]=1,表示该顶点已经使用(已经连通)。
  3. 若集合U中顶点ui与顶点V-U中的顶点vj之间存在边,则寻找这些边中的权值最小的边,但不构成回路,将顶点vj加入集合U中,将边(ui,vj)加入集合D中,标记visted[u]=1
  4. 重复步骤2,直到U与V相等,即所有顶点都被标记为已经访问过,此时D中有N-1条边

估计看了这个思路,人都蒙了,没事,继续看看下面的图解就会一目了然了。

image-20231227205959320


三、Prim算法实战

1584. 连接所有点的最小费用 - 力扣(LeetCode)

在力扣1584题,是求坐标轴上的点的最小生成树,具体题目请看上述链接。

解题思路:使用Prim算法。

  1. 根据顶点的信息,生成邻接表
  2. 定义几个变量
    • record:记录已经使用过的点
    • recordDistance: 用来存储每个未被选中的点到record的最短距离。若已经被放入record中则设置为-1
  3. 初始化变量
    • 将第0个顶点作为生成最小生成树的起始顶点
    • 初始化recordDistance,记录其他未使用的订单到最小生成树的最小距离,由于一开始最小生成树只有一个节点,于是最小距离就是其余顶点到这个最小生成树的节点的距离,也就是weight[0][i]
  4. 开始构造最小生成树
    • 遍历recordDistance,找出其余顶点到最小生成树的最小距离,记录其下标以及最小距离。
    • 收集得到的最小距离
    • 将该下标的recordDistance最小距离设置为-1,表示已经使用了
      1. 更新recordDistance数组,更新其余顶点到最小生成树的最小距离,Math.min(recordDistance[i], weight[minIndex][i]),因为最小生成树新增了一个节点,那么有可能导致其他顶点到这个新增的节点的距离更近,于是需要更新recordDistance
class Solution {
    public int minCostConnectPoints(int[][] points) {
        // 最终结果
        int result = 0;
        // 邻接表
        int[][] weight = new int[points.length][points.length];
        // 初始化邻接表
        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < points.length; j++) {
                weight[i][j] = weight[j][i] = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
            }
        }
        // 记录已经使用过的点
        List<Integer> record = new ArrayList<>();
        // 记录其余点到上一个点的距离,如果为-1,说明该点已经使用了
        int[] recordDistance = new int[points.length];
        // 将第0个点设置为顶点
        record.add(0);
        recordDistance[0] = -1;
        // 更新距离
        for (int i = 1; i < points.length; i++) {
            recordDistance[i] = weight[0][i];
        }
        // 开始找点
        while (record.size() < points.length) {
            // 距离最短的顶点下标
            int minIndex = 0;
            // 最短距离
            int minDistance = Integer.MAX_VALUE;
            for (int i = 0; i < recordDistance.length; i++) {
                if (recordDistance[i] != -1 && recordDistance[i] < minDistance) {
                    minIndex = i;
                    minDistance = recordDistance[i];
                }
            }
            record.add(minIndex);
            result += minDistance;
            recordDistance[minIndex] = -1;
            // 更新顶点对应的最小距离
            for (int i = 0; i < points.length; i++) {
                if (recordDistance[i] != -1){
                    recordDistance[i] = Math.min(recordDistance[i], weight[minIndex][i]);
                }
            }

        }
        return result;
    }
}

文章来源:https://blog.csdn.net/weixin_51146329/article/details/135256313
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。