代码随想录算法训练营第五十六天|prim算法、kruskal算法

题目链接53. 寻宝解题思路prim 算法具体思路首先读取节点数 v 和边数 e构建大小为 (v 1) * (v 1) 的邻接矩阵 graph初始值设为 10001 表示节点间无直接边适配权值不超过 10000 的场景输入 e 条无向边的两个端点 v1​v2 ​和权值 val将 graph[v1][v2] 和 graph[v2][v1] 均赋值为 val无向图双向存储边权初始化标记数组 intree 长度 v 1初始 false标记节点是否已加入最小生成树和距离数组 distance长度 v 1初始 10001记录每个节点到当前生成树的最小权值距离随后循环 v - 1次最小生成树含v个节点需添加v−1条边每次遍历所有节点找到未加入生成树且 distance 值最小的节点 cur将 cur 标记为已加入生成树再遍历所有节点若节点未加入生成树且 cur 到该节点的边权小于其当前 distance 值则更新 distance 为更小的边权循环结束后累加 distance 数组中 2 到 v 节点的权值最终输出该累加和即为最小生成树的总权值。具体代码#includeiostream #includevector #include climits using namespace std; int main () { int v; int e; cin v e; vectorvectorint graph(v 1, vectorint(v 1, 10001)); for (int i 0; i e; i) { int v1; int v2; int val; cin v1 v2 val; graph[v1][v2] val; graph[v2][v1] val; } vectorbool intree(v 1, false); vectorint distance(v 1, 10001); for (int i 1; i v; i) { int cur -1; int minval INT_MAX; for (int j 1; j v; j) { if (!intree[j] distance[j] minval) { minval distance[j]; cur j; } } intree[cur] true; for (int j 1; j v; j) { if (!intree[j] graph[cur][j] distance[j]) distance[j] graph[cur][j]; } } int ans 0; for (int i 2; i v; i) { ans distance[i]; } cout ans endl; }解题思路kruskal 算法 并查集具体思路首先定义 Edge 结构体存储边的两个端点 v1v2 和权值 val实现并查集核心函数init 初始化父节点为自身、find 带路径压缩查找节点根节点、join 合并两个节点所在集合定义排序比较函数cmp 使边按权值升序排列主函数中读取节点数 v 和边数 e创建存储 e 条边的数组 edges 并输入每条边的端点和权值对 edges 按权值升序排序保证优先选权值小的边初始化并查集父节点数组遍历排序后的所有边对每条边查找两个端点的根节点若根节点不同说明加入该边不会形成环符合最小生成树无环要求则将该边的权值累加到结果 ans 中并合并两个端点所在的集合遍历完成后输出 ans即为最小生成树的总权值。具体代码#includeiostream #includevector #include algorithm using namespace std; struct Edge { int v1; int v2; int val; }; int n 10001; vectorint father(n, -1); void init() { for (int i 0; i n; i) father[i] i; } int find (int u) { if (u father[u]) return u; else return father[u] find(father[u]); } void join(int u, int v) { u find(u); v find(v); if (u v) return; else father[v] u; } static bool cmp (Edge a, Edge b){ return a.val b.val; } int main () { int v; int e; cin v e; vectorEdge edges(e); for (int i 0; i e; i) { cin edges[i].v1 edges[i].v2 edges[i].val; } sort(edges.begin(), edges.end(), cmp); init(); int ans 0; for (int i 0; i edges.size(); i) { Edge edge edges[i]; int u find(edge.v1); int v find(edge.v2); if (u ! v) { ans edge.val; join(u, v); } } cout ans endl; }