算法日记20：SC72最小生成树（prim朴素算法）

一、题目：

二、题解

2.1：朴素prim的步骤解析 O ( n 2 ) O(n^2) O(n2)(n<=1e3) 0、假设，我们现在有这样一个有权图

1、我们随便找一个点，作为起点开始构建最小生成树(一般是1号)，并且存入intree[]状态数组中（该数组表示是否访问过了）

2、找所有点当中，距离intree[]最近的点， 循环 n − 1 n-1 n−1次(因为已经确定了1这个点)，每次找距离intree[]最近的点作为拓展点，即选择了[2]这个点 3、把dis[2](2距离intree的距离)累计起来(res+=dis[2])，并且更新所有点的dis值

4、此时，重复找所有点当中，距离intree[]最近的点(重复2/3)… 三、朴素prim代码解析 3.1、代码分块解析：

这段代码实现了 Prim 算法 用于求解 最小生成树，我会将代码分块并逐步解释每一块的作用。

1. 常量定义 const int N = 103; // 设置最大点数 int a[N][N], dis[N]; bool st[N]; int n, m;

解释:

N 定义了图中点的最大数量，设置为 103。a[N][N]：一个二维数组，表示图的邻接矩阵，存储两点之间的边权。 a[i][j]：表示i–>j的距离 dis[N]：一个一维数组，表示从起始点到每个节点的最短距离。st[N]：布尔型数组，用来标记某个节点是否已经被加入最小生成树。(图解中的intree数组)n 和 m：分别表示图中的节点数和边数。 2. solve 函数的初始化 void solve() { memset(dis, 0x3f, sizeof(dis)); // 初始化dis数组，设为最大值 memset(a, 0x3f, sizeof(a)); // 初始化邻接矩阵为最大值 // 初始化 cin >> n >> m; for (int i = 1; i <= m; i++) { int ui, vi, wi; cin >> ui >> vi >> wi; a[ui][vi] = min(a[ui][vi], wi); a[vi][ui] = min(a[vi][ui], wi); } for (int i = 1; i <= n; i++) a[i][i] = 0; // 自己到自己没有边，权重为 0

解释:

memset(dis, 0x3f, sizeof(dis))：将 dis 数组初始化为一个较大的值（通常为无穷大，表示尚未连接的节点）。memset(a, 0x3f, sizeof(a))：将邻接矩阵 a 初始化为无穷大，表示两点之间如果没有边，则权重为无穷大。输入节点数 n 和边数 m，然后读入每条边的信息，更新邻接矩阵 a。同时，因为有可能存在重复边，所以采用 min 取最小边权，确保保存的是权重最小的边。设置每个节点到自身的距离为 0。 3. 最小生成树的 Prim 算法核心部分 dis[1] = 0; // 从节点1开始，初始权重为0 int res = 0; // 记录最小生成树的总权重 for (int i = 1; i <= n; i++) // 进行n次选择最小值操作 { int temp = -1; // 用于记录当前最小值对应的节点 // 遍历所有节点，找出距离最小的未加入最小生成树的节点 for (int j = 1; j <= n; j++) { //和Dijkstra一样, //1.当j这个点还没访问过，2.遍历的的点j<当前点temp的距离,那么就更新temp //temp==-1只是为了确保其能够第一次进入循环，详解看Dijkstra if (!st[j] && ((temp == -1) || (dis[j] < dis[temp]))) { temp = j; } } //此时temp就是距离intree最近的点 if (temp == -1) // 如果所有节点都已经被选中，说明图不连通,直接return { cout << -1 << '\n'; return; }

解释:

初始化 dis[1] = 0，表示从节点 1 开始构建最小生成树，起始点的距离为 0。res 用来记录最小生成树的总权重。外层 for (int i = 1; i <= n; i++) 进行 n 次选择最小值操作，每次选择一个最小的未加入最小生成树的节点。内层循环 for (int j = 1; j <= n; j++) 遍历所有节点，找出距离当前生成树最近的节点。条件是节点未加入生成树 !st[j] 且 dis[j] 小于当前最小值。temp == -1 用来判断是否图不连通。如果没有找到最小值节点，说明图是断开的，输出 -1。 4. 更新最小生成树的权重并松弛边 res += dis[temp]; // 将当前最小值加到结果中 st[temp] = true; // 标记节点temp已加入最小生成树 dis[temp] = 0; // 当前节点到自己的距离设为0（实际上不影响结果） for (int i = 1; i <= n; i++) { // 松弛与temp相连的所有边 if (!st[i]) { // 只有未加入最小生成树的节点才能被松弛 dis[i] = min(dis[i], a[temp][i]); } } } cout << res << '\n'; // 输出最小生成树的总权重 }

解释:

将选中的最小值节点 temp 的距离 dis[temp] 加到总权重 res 中。标记该节点已经被加入最小生成树，即 st[temp] = true。进行 松弛操作，尝试更新与当前最小值节点相连的所有边的权重，更新未加入生成树的节点的最短距离 dis[i]。 3.2、完整代码 #include<bits/stdc++.h> using namespace std; const int N=103; struct node{ int v;//指向点 int w;//权重 }; int a[N][N],dis[N]; bool st[N]; int n,m; void solve() { memset(dis,0x3f,sizeof(dis)); memset(a,0x3f,sizeof(a)); //初始化 cin>>n>>m; for(int i=1;i<=m;i++) { int ui,vi,wi;cin>>ui>>vi>>wi; //g[ui].push_back({vi,wi}); a[ui][vi]=min(a[ui][vi],wi); a[vi][ui]=min(a[vi][ui],wi); } for(int i=1;i<=n;i++) a[i][i]=0; dis[1]=0; //从1开始，1的权重为0 int res=0; for(int i=1;i<=n;i++) //找n次最小值 { int temp=-1; //表示dis最小点 for(int j=1;j<=n;j++) //遍历每个点找最小值 { //如果j还没被选中过 if(!st[j] && ((temp==-1)||(dis[j]<dis[temp]))) { temp=j; } } if (temp == -1) // 如果没有点可选，说明图不连通 { cout<<-1<<'\n'; break; } //此时表示已经选中了最小值temp res+=dis[temp]; st[temp]=true; dis[temp]=0;//距离设置为0 for(int i=1;i<=n;i++) //松弛temp相连的边a[temp][i] { if(!st[i]) //表示i话没有松弛过 { dis[i]=min(dis[i],a[temp][i]); } } } cout<<res<<'\n'; } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int _=1; while(_--) solve(); return 0; }