最小生成树 – Prim算法

最小生成树是所有节点的最小连通子图， 即：以最小的成本（边的权值）将图中所有节点链接到一起。

图N个节点，E条边，则最小生成树就是从E条边种选取N-1条边的总权重值最小。

Prim算法的原理是贪心算法，即每次都将离最小生成树最近距离的边接入最小生成树。

Prim算法必备两个数组：

• minDist：记录距离最小生成树节点的距离。
• isInTree：记录节点是否已经在最小生成树中。

Prim算法三部曲：

• 1 找到距离最小生成树最近的节点
• 2 将距离最小生成树最近的节点加入最小生成树
• 3 更新最小生成树到其他节点的距离

以下为代码随想录的模拟步骤：

初始图状态：

此时没有最小生成树，先选择节点1作为距离最小生成树最近节点，加入最小生成树，更新minDist。

isInTree=[1]

此时2,3都是距离最小生成树最近的节点，选择2，更新minDist。

isInTree=[1, 2]

此时3,6都是最近点，选择3，更新minDist。

isInTree=[1， 2， 3]

此时4,6都是最近点，选择4，更新minDist。

isInTree=[1， 2， 3， 4]

此时5，6是最近点，选,5，更新minDist。

isInTree=[1， 2， 3， 4， 5]

此时6,7是最近点，选,6，更新minDist。

isInTree=[1， 2， 3， 4， 5，6]

最后加入7.

模拟完了之后，我们来上真题吧。

解题思路：

• 1 处理输入
• 2 Prim算法3部曲
  • 2.1 在未访问过的minDist中找最小的节点i
  • 2.2 将节点i的isInTree设置为True
  • 2.3 在未访问过的从节点i起始的边里找比minDist还小的边

代码如下：

#include iostream>
#include vector>
#include climits>
using namespace std;

int main(){
    
    int v, e;
    int x, y, z;
    cin >> v >> e;
    vector<vector> grid(v+1, vector(v+1, 10001));
    while(e--){
        cin >> x >> y >> z;
        grid[x][y] = z;
        grid[y][x] = z;
    }
    
    // prim 必备数组
    vector minDist(v+1, 10001);
    vector isInTree(v+1, false);
    
    // prim 需要v-1个节点
    for(int i=1; i<v; i++){
        // prim 3部曲
        // 1 找到距离最小生成树最近的节点
        int minValue = INT_MAX;
        int cur = -1;
        for(int j=1; j<=v; j++){ if (!isInTree[j] && minValue>minDist[j]){
                minValue = minDist[j];
                cur = j;
            }
        }
        
        // 2 将离最小生成树最近的节点加入最小生成树
        isInTree[cur] = true;
        
        // 3 更新minDist
        for(int j=1; j<=v; j++){
            if (!isInTree[j] && grid[cur][j] < minDist[j]){
                minDist[j] = grid[cur][j];
            }
        }
    }
    
    // prim 计算minDist数组的最短路径
    int result = 0;
    for (int i = 2; i <= v; i++) { // 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1条边
        result += minDist[i];
    }
    cout << result << endl;
}