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

一、题目：

二、题解

2.1：朴素prim的步骤解析$O(n^2)$(n<=1e3)

0、假设，我们现在有这样一个有权图

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

2、找所有点当中，距离intree[]最近的点，

• 循环$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;
}