课堂笔记

Yuilice

2025-04-19 20:00:34

发布于：浙江

20阅读

0回复

0点赞

Prim算法

实现思想

准备工作

在图当中选择一个顶点作为起点。
建立一个dis数组，dis[i]代表了i号顶点加入生成树的最短距离。
建立一个vis数组，vis[i]表示i号顶点是否已经被访问过。
将起点距离生成树的最短距离更新为0，即dis[start] = 0

算法运行

根据贪心思想，每一次挑选一个距离生成树最近的顶点，加入生成树，并更新距离生成树的最短距离。

找到距离生成树最近的顶点,加入生成树。
通过新加入生成树顶点的相邻顶点,更新其相邻顶点的到达生成树的最短距离。
重复步骤1和步骤2，直到生成树的顶点数等于图的顶点数。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5 ;  // 设置顶点的最大数量
int dis[MAXN]; // 记录每个顶点到生成树的最短距离
bool vis[MAXN];// 记录每个顶点是否已经被访问过
int n, m; // 图的顶点数和边数
struct Node{
    int v,w; // 边的终点和权重
};
vector<Node> G[MAXN]; // 邻接表

int main(){
    cin >> n >> m; // 输入图的顶点数和边数
    while(m--){
        int u,v,w;
        cin >> u >> v >> w; // 输入边的终点和权重
        G[u].push_back({v,w}); // 将边加入邻接表
        // G[v].push_back({u,w}); // 若是无向图则将边加入邻接表
    }
    // Prim算法
    for(int i = 0 ; i <= n ; i ++ )dis[i] = INT_MAX; // 初始化距离生成树的最短距离
    dis[1] = 0 ; // 起点距离生成树的最短距离为0
    for(int i = 1 ; i <= n ; i ++ ){
        // 选择n次距离生成树最近的顶点
        int pos = 0; // 距离生成树最近的顶点
        for(int j = 1 ; j <= n ; j ++ ){
            if(!vis[j] && dis[j] < dis[pos]){
                // 找到距离生成树最近的顶点
                pos = j ; // 更新距离生成树最近的顶点
            }
        }
        if(pos == 0){
            break ; // 所有顶点都已经被访问过或者无法构成生成树
        }
        // 加入生成树
        vis[pos] = true ; // 标记该顶点已经被访问过
        for(int j = 0 ;j< G[pos].size() ; j ++ ){
            int v = G[pos][j].v ; // 边的终点
            int w = G[pos][j].w ; // 边的权重
            if(!vis[v] && dis[v] > w){
                // 更新距离生成树的最短距离
                dis[v] = w ;
            }
        }
    }
    long long answer = 0 ; // 记录最小生成树的权重
    for(int i = 1 ; i <= n ; i ++ ){
        answer += dis[i]; // 累加所有顶点到生成树的距离
    }
    cout << answer << endl; // 输出最小生成树的权重
    return 0;
}