算法日记21:SC72（最小生成树）：prim的priority_queue()堆优化

一、题目：

二、题解：

2.1：在朴素算法中，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; 
       }

2.2、我们只是想依次取出距离最小的点，因此想到可以使用优先队列优化.

0）假设我们现在有这样一幅图

1）首先我们把[1]这个点放入优先队列里面，while[pq.size()]中挨个top+pop,此时[1]这个点就是距离intree[]最近的点

2）枚举[1]的所有出边，来更新dis[i]

• 更新之后，图变成了:
  

3）此时，我们把[1]和[4]存入intree[]当中

4）由于priority_queue()的特性，我们会取出[{2,1}]，即此时[2]为距离原点最近的点，并且枚举[2]的所有出边，来更新dis[i]…

• 重复2)、3)操作

5）总结：

三、代码解析：

3.1代码分块

这份代码是实现了 Prim 算法，通过优先队列（小根堆）来优化求解最小生成树（MST）。我们可以将它分成几个部分来逐步解析：

1. 节点结构体定义和优先队列的自定义比较规则

struct node{
   int v;   //点
   int w;   //权重
   bool operator < (const node& u)const //重写<，构建小根堆
   {
        return w == u.w ? v < u.v : w > u.w;
   }
};

• node 结构体用于表示图中的边。每个节点包含两个信息：

  • v：表示节点编号。
  • w：表示边的权重。

• operator <：这是重载小于运算符，用来指定优先队列的排序规则：

  • 如果两个节点的权重相同，按照节点编号 v 的大小进行排序。
  • 否则，按照权重 w 大小进行降序排序（这里为了实现小根堆，较小的权重在堆顶）。

2. 变量声明

vector<node>g[N]; // 存储图的邻接表
int dis[N]; // 存储从源节点到每个节点的最短距离
bool st[N]; // 状态数组，记录节点是否已加入最小生成树
int n,m; // n为节点数，m为边数

• g[N]：邻接表，用来存储图的边。每个节点有一个 vector<node> 来存储与它相连的其他节点和对应的边权重。
• dis[N]：最短距离数组，dis[i] 记录从源节点到节点 i 的最短距离。
• st[N]：状态数组，用来标记某个节点是否已经被加入最小生成树（MST）。
• n 和 m：分别表示节点数和边数。

3. solve 函数：核心算法实现

void solve()
{
   memset(dis,0x3f,sizeof(dis)); // 初始化所有距离为最大值

   cin >> n >> m;
   for(int i = 1; i <= m; i++) {
       int ui, vi, wi;
       cin >> ui >> vi >> wi;    
       g[ui].push_back({vi, wi});    // ui->vi，权重为wi
       g[vi].push_back({ui, wi});    // 对无向边的处理
   }

• memset(dis, 0x3f, sizeof(dis));：初始化 dis 数组的所有值为一个很大的数（0x3f 表示的值是 63 或 63的高位），这是为了模拟无穷大，表示初始时从源节点到其他节点的距离都是未知的。
• 接着输入 n 和 m，表示节点数和边数。
• 通过 for 循环读取每一条边，存入邻接表 g 中，注意无向图需要将每条边都存两次（g[ui].push_back({vi, wi}) 和 g[vi].push_back({ui, wi})）。

4. 初始化和优先队列操作

   int res = 0;
   dis[1] = 0; // 从节点 1 开始，起点到自己的距离为 0
   st[1] = true; // 标记节点 1 已经加入 MST

   priority_queue<node> pq;
   pq.push({1, 0}); // 将起点 1 入堆，权重为 0

• dis[1] = 0：设定起始节点（这里选择节点 1）的距离为 0。
• st[1] = true：标记起点已经被加入 MST。
• priority_queue<node> pq：创建一个优先队列（小根堆），用于每次选择当前最小权重的节点。
• pq.push({1, 0})：将起点节点 1 和它的距离（0）加入优先队列。

5. 主循环：构建最小生成树

   while(pq.size()) { // 堆非空，继续进行
        auto t = pq.top().v; pq.pop(); // 取出堆顶节点
        st[t] = true; // 标记当前节点已经加入 MST
        res += dis[t]; // 累加当前节点的最小距离到结果
        dis[t] = 0; // 将该节点的距离置为 0

        for(auto &x : g[t]) { // 遍历所有与 t 相连的节点
            int y = x.v;  // 目标节点
            int w = x.w;  // 边的权重

            if(!st[y] && (dis[t] + w) < dis[y]) { // 如果目标节点还没加入 MST 且新的距离更小
                dis[y] = dis[t] + w; // 更新最短距离
                pq.push({y, dis[y]}); // 将更新后的节点加入堆
            }
        }
   }

• while(pq.size())：当优先队列不为空时，继续处理。
• auto t = pq.top().v; pq.pop();：取出并弹出堆顶元素（当前距离最小的节点）。
• st[t] = true;：标记节点 t 已加入 MST。
• res += dis[t];：将当前节点的最短距离累加到结果 res 中。
• dis[t] = 0;：将该节点的距离置为 0，表示已经处理过。
• for(auto &x : g[t])：遍历当前节点 t 所有相邻的边，更新相邻节点的距离。

6. 检查最小生成树是否构建完整

   for(int i = 1; i <= n; i++) 
       if(st[i] == false) res = -1;  // 如果有节点没有被访问过，说明无法构建 MST
   cout << res << '\n';
}

• for 循环检查是否所有节点都已经被加入到 MST。如果有节点没有被访问到，则返回 -1 表示无法构成最小生成树（即图不连通）。
• 如果所有节点都在 MST 中，则输出结果 res。

3.2：完整代码解析：

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+7;
struct node{
   int v;   //点
   int w;   //权重
   bool operator < (const node& u)const //重写<，构建小根堆
   {
        return w == u.w ? v < u.v : w > u.w;
   }
};
vector<node>g[N];
int dis[N]; //距离数组
bool st[N]; //状态数组intree
int n,m;


void solve()
{
   memset(dis,0x3f,sizeof(dis));

   //初始化
   cin>>n>>m;
   for(int i=1;i<=m;i++)
   {
       int ui,vi,wi;cin>>ui>>vi>>wi;    
       g[ui].push_back({vi,wi});    //ui->vi，权重为wi
       g[vi].push_back({ui,wi});    //对无向边的处理
   }
   
    int res=0;
    dis[1]=0; //从1开始，1的权重为0
    st[1]=true;

    priority_queue<node>pq;
    pq.push({1,0}); //从1开始，权重为0
    
   while(pq.size()) //堆非空
   {
        auto t=pq.top().v;pq.pop();    //取出+弹出堆顶

        //选择t这个点  
        st[t]=true;
        res+=dis[t];   //累计t的权重
        dis[t]=0; //把t距离清0

        for(auto &x:g[t]) //取出t所有指向的边
        {
            int y=x.v;  //取出x的指向点+指向边的权重
            int w=x.w;
            
            //目标点没有被访问过
            //当前点的权重+w<目标点的权重
            if(!st[y] && (dis[t]+w)<dis[y])
            {
                dis[y]=dis[t]+w;
                pq.push({y,dis[y]});
            }
        }
   }
   //不存在最小生成树
   for(int i=1;i<=n;i++) if(st[i]==false) res=-1; 
    cout<<res<<'\n';
} 

   

int main()
{
   ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
   int _=1;
   while(_--) solve();
   return 0;
}