算法——最小生成树

文章目录一、最小生成树概述二、Prim算法三、Kruskal算法一、最小生成树概述最小生成树这一概念最初主要是为加权连通无向图量身打造的。不过在有向图领域也衍生出了与之类似的拓展性概念。而本课程所涉及的内容主要围绕加权连通无向图来逐步展开以此来探讨最小生成树相关知识。对于一个加权连通无向图 G(V,E)其中V是图的顶点集合E是图的边集合每一条边 (u,v)∈E都有一个对应的权重w(u,v)。最小生成树是图G的一个子图它满足以下条件连通性这个子图是连通的也就是说对于图中任意两个顶点都存在一条路径可以从一个顶点到达另一个顶点。包含所有顶点子图包含了原图 G中的所有顶点 V。无环子图中不包含任何回路环即不存在一条从某个顶点出发经过若干条边后又回到该顶点的路径。最小权重在所有满足上述三个条件的子图中这个子图的所有边的权重之和是最小的。二、Prim算法普里姆Prim算法同样是贪心算法它从图中的任意一个顶点开始每次选择与当前已加入最小生成树的顶点集合相连的边中权重最小的边将对应的顶点加入到最小生成树的顶点集合中直到所有顶点都被加入。普利姆算法的处理步骤如下选择起始顶点从图中任意选择一个顶点作为起始点将其加入最小生成树的顶点集合。选择最小边在所有一个端点在最小生成树顶点集合中另一个端点不在该集合中的边中选择权重最小的边。扩展生成树将步骤 2 中选择的边加入最小生成树的边集并将该边不在最小生成树顶点集合中的端点加入到该集合中。重复步骤 2 和 3不断重复步骤 2 和 3直到最小生成树的顶点集合包含图中的所有顶点。对应C代码int main() { int v, e; int x, y, k; cin v e; // 填一个默认最大值题目描述val最大为10000 vectorvectorint grid(v 1, vectorint(v 1, 10001)); while (e--) { cin x y k; // 因为是双向图所以两个方向都要填上 grid[x][y] k; grid[y][x] k; } // 所有节点到最小生成树的最小距离 vectorint minDist(v 1, 10001); // 这个节点是否在树里 vectorbool isInTree(v 1, false); // 我们只需要循环 n-1次建立 n - 1条边就可以把n个节点的图连在一起 for (int i 1; i v; i) { // 1、prim三部曲第一步选距离生成树最近节点 int cur -1; // 选中哪个节点 加入最小生成树 int minVal INT_MAX; for (int j 1; j v; j) { // 1 - v顶点编号这里下标从1开始 // 选取最小生成树节点的条件 // 1不在最小生成树里 // 2距离最小生成树最近的节点 if (!isInTree[j] minDist[j] minVal) { minVal minDist[j]; cur j; } } // 2、prim三部曲第二步最近节点cur加入生成树 isInTree[cur] true; // 3、prim三部曲第三步更新非生成树节点到生成树的距离即更新minDist数组 // cur节点加入之后 最小生成树加入了新的节点那么所有节点到 最小生成树的距离即minDist数组需要更新一下 // 由于cur节点是新加入到最小生成树那么只需要关心与 cur 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢 for (int j 1; j v; j) { // 更新的条件 // 1节点是 非生成树里的节点 // 2与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小 // 很多录友看到自己 就想不明白什么意思其实就是 cur 是新加入 最小生成树的节点那么 所有非生成树的节点距离生成树节点的最近距离 由于 cur的新加入需要更新一下数据了 if (!isInTree[j] grid[cur][j] minDist[j]) { minDist[j] grid[cur][j]; } } } // 统计结果 int result 0; for (int i 2; i v; i) { // 不计第一个顶点因为统计的是边的权值v个节点有 v-1条边 result minDist[i]; } cout result endl; }三、Kruskal算法克鲁斯卡尔Kruskal算法是一种贪心算法它的核心思路是将图中所有的边按照权重从小到大进行排序然后依次选取权重最小的边只要加入这条边不会形成环就将其纳入最小生成树的边集直到最小生成树包含图中的所有顶点。该算法的具体处理步骤如下排序边把图中所有的边按照权重从小到大进行排序。初始化并查集为图中的每个顶点创建一个独立的集合用于后续判断加入边时是否会形成环。选择边从排序好的边列表中依次选取边如果该边连接的两个顶点不在同一个集合中即加入这条边不会形成环则将这条边加入最小生成树的边集并将这两个顶点所在的集合合并。重复步骤 3不断重复步骤 3直到最小生成树的边数达到顶点数减 1此时就得到了图的最小生成树。在判断加入一条边是否会形成环时可以使用并查集。如果边的两个端点属于不同的集合说明加入这条边不会形成环将这两个集合合并如果属于同一个集合则跳过这条边。对应C代码// l,r为 边两边的节点val为边的数值 struct Edge { int l, r, val; }; // 节点数量 int n 10001; // 并查集标记节点关系的数组 vectorint father(n, -1); // 节点编号是从1开始的n要大一些 // 并查集初始化 void init() { for (int i 0; i n; i) { father[i] i; } } // 并查集的查找操作 int find(int u) { return u father[u] ? u : father[u] find(father[u]); // 路径压缩 } // 并查集的加入集合 void join(int u, int v) { u find(u); // 寻找u的根 v find(v); // 寻找v的根 if (u v) return ; // 如果发现根相同则说明在一个集合不用两个节点相连直接返回 father[v] u; } int main() { int v, e; int v1, v2, val; vectorEdge edges; int result_val 0; cin v e; while (e--) { cin v1 v2 val; edges.push_back({v1, v2, val}); } // 执行Kruskal算法 // 按边的权值对边进行从小到大排序 sort(edges.begin(), edges.end(), [](const Edge a, const Edge b) { return a.val b.val; }); // 并查集初始化 init(); // 从头开始遍历边 for (Edge edge : edges) { // 并查集搜出两个节点的祖先 int x find(edge.l); int y find(edge.r); // 如果祖先不同则不在同一个集合 if (x ! y) { result_val edge.val; // 这条边可以作为生成树的边 join(x, y); // 两个节点加入到同一个集合 } } cout result_val endl; return 0; }