【代码随想录day57】【C++复健】 53. 寻宝（prim算法）；53. 寻宝（kruskal算法）

53. 寻宝（prim算法）

好像在研究生的算法课上学过prim算法和kruskal算法，不过当时只是了解了一下大致的概念和流程，并没有涉及到如何去写代码的部分，今天也算是学习了一下这两个算法的代码应该如何去实现，还是挺长见识的。

整体做的时候，是一个边看解析边自己做的过程，因为我自己哪怕是看完了卡哥的思路解析仍然有很多不是很确定的地方，这些地方也相当容易出错，一一列举一下遇到的各种疑问：

1 我在定义这个图的时候应该用邻接矩阵还是邻接表？

问了下GPT说是都可以，那当然还是用邻接数组会更好实现一点。并且本题当中边还是很密集的。

2 mindist和inTree如何定义？

一维即可，长度为v+1，因为0号位我们会进行弃用。

3 是否需要专门的处理初始化逻辑的代码？

从卡哥写的代码里还是能看出来是不需要的，只要我们一开始给dis定义成最大值或者比10001更大的值，就会自动把第一个节点放进去，并且顺便更新一下mindist。

解决这三个问题之后，整个prim算法的逻辑因为已经看过解析的思路了，反而自己也能写出来了。

#include<iostream>
#include<vector>
using namespace std;int main(){int v,e;cin >> v >> e;vector<vector<int>> grid(v+1, vector<int>(v+1, 10001));for(int i=0; i<e; i++){int left, right, weight;cin >>  left >> right >> weight;grid[left][right] = weight;grid[right][left] = weight;}vector<int> mindist(v+1, 10001);vector<bool> inTree(v+1);int result = 0;for(int i=0; i<v; i++){int dis = 10002;int pos = -1;for(int j=1; j<=v; j++){if(!inTree[j] && mindist[j] < dis){dis = mindist[j];pos = j;}}if(i != 0){result += dis;}inTree[pos] = true;for(int k=1; k<=v; k++){if(!isInTree[j] && grid[pos][k] < mindist[k]){mindist[k] = grid[pos][k];}}}cout << result;return 0;
}

53. 寻宝（kruskal算法）

同样是看了思路之后尝试自己实现，不过自己想去实现当然也是有不小的难度的。

1 看了解释知道要保存变并且按照权值排序，但应该怎么做？

想了一下好像邻接矩阵和邻接表都不太好的样子，但是自己又不知道用什么，最后一看解析，好嘛，结构体，这个是真的想不到，毕竟从学图论开始就没用过这个东西。包括后面这个vector<edge>，也是没想到还可以这么用。

2 sort函数，哪个库的，怎么用？

因为忘写#include <algorithm>而没过。不过比起这个倒不如说，根本就没有写的意识，不知道sort函数还得调个库。然后就是老生常谈的传cmp问题，如果是在类内的话需要写的很复杂：

    static bool cmp(const Edge& a, const Edge& b) {return a.val < b.val;}

 原因都忘记了，问问GPT复习一下：
 

• 普通成员函数 默认包含一个隐式的 this 指针参数，指向调用它的对象。
• 例如，cmp 在类内是一个普通成员函数时，其实际签名类似于：

  bool cmp(const Edge& a, const Edge& b, Solution* this);

  这使得它只能通过具体的类对象调用，或者通过对象的指针调用。
• 但是 std::sort 接受的是一个普通函数指针，不支持这种额外的 this 参数，因此直接传递普通成员函数会出错。

但是这次是在类外。所以简单这么写也不会报错：

bool cmp(Edge a, Edge b){return a.val < b.val;
}

或者像卡哥的写法一样用lambda表达式：

    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {return a.val < b.val;});

3 试图去写一个intree变量统计点在不在里面，但并查集就是干这个用的。所以理解的还不是很到位。

#include<iostream>
#include<vector>
#include <algorithm> // for sort
using namespace std;vector<int> father;struct Edge {int l, r, val;
};void init(){for(int i=0; i<father.size(); i++){father[i] = i;}
}int find(int u){return u==father[u] ? u: father[u] = find(father[u]);
}bool issame(int u, int v){u = find(u);v = find(v);return u == v;
}
bool join(int u, int v){u = find(u);v = find(v);if(u==v){return false;}father[v] = u;return true;
}bool cmp(Edge a, Edge b){return a.val < b.val;
}int main(){int v,e;cin >> v >> e;father = vector<int> (v+1);init();int sum = 0;vector<Edge> edges;for(int i=0; i<e; i++){int left, right, weight;cin >>  left >> right >> weight;edges.push_back({left, right, weight});}sort(edges.begin(), edges.end(), cmp);for(int i=0; i<e; i++){bool result = join(edges[i].l, edges[i].r);if(result){sum += edges[i].val;}}cout << sum;return 0;
}