网站侧边栏代码电商网站支付体系建设特点

网站侧边栏代码,电商网站支付体系建设特点,php网站 怎么取得后台管理权限,动漫与游戏制作专业有前途吗目录 前言 一、最小生成树的核心概念#xff1a;先搞懂 “是什么” 1.1 生成树的定义 1.2 最小生成树的定义 1.3 最小生成树的性质 1.4 最小生成树的适用场景 二、Prim 算法#xff1a;“加点法” 构建最小生成树 2.1 Prim 算法的基本思想 2.2 Prim 算法的图解过程 …目录前言一、最小生成树的核心概念先搞懂 “是什么”1.1 生成树的定义1.2 最小生成树的定义1.3 最小生成树的性质1.4 最小生成树的适用场景二、Prim 算法“加点法” 构建最小生成树2.1 Prim 算法的基本思想2.2 Prim 算法的图解过程2.3 Prim 算法的代码实现邻接矩阵版代码说明2.4 Prim 算法的代码实现邻接表版代码说明2.5 Prim 算法的时间复杂度分析三、Kruskal 算法“加边法” 构建最小生成树3.1 Kruskal 算法的基本思想3.2 Kruskal 算法的图解过程3.3 Kruskal 算法的代码实现并查集 排序代码说明3.4 Kruskal 算法的时间复杂度分析3.5 并查集的优化路径压缩 按秩合并四、Prim 算法与 Kruskal 算法的对比该选哪一个选择建议五、经典例题实战从模板到应用例题 1买礼物洛谷 P1194题目描述输入格式输出格式示例输入 2示例输出 2解法分析代码实现例题 2滑雪洛谷 P2573题目描述输入格式输出格式示例输入示例输出解法分析代码实现总结前言在图论的世界里有这样一个经典问题给定一个连通图如何找到一棵包含所有顶点、边权之和最小的树这就是最小生成树Minimum Spanning Tree简称 MST要解决的核心问题。小到城市间的公路规划、通信网络搭建大到芯片布线、物流路径优化最小生成树都发挥着至关重要的作用 —— 它能在保证 “连通性” 的前提下实现 “成本最小化”堪称图论中的 “性价比之王”。如果你是算法初学者可能会对 “生成树”“贪心策略” 这些概念感到困惑如果你是有一定基础的开发者或许想深入理解两种经典算法的底层逻辑与适用场景。本文将从最小生成树的基本概念出发用通俗的语言拆解 Prim 算法和 Kruskal 算法的实现细节结合大量图解和可直接运行的 C 代码再通过 5 道经典例题巩固实战能力。无论你是学生还是职场人相信都能从这篇文章中有所收获。下面就让问我们正式开始吧一、最小生成树的核心概念先搞懂 “是什么”在正式讲解算法之前我们必须先理清几个关键概念 —— 只有地基打牢了后续的算法学习才能事半功倍。1.1 生成树的定义首先我们回顾一下“生成树”的概念。对于一个连通无向图G(V,E)生成树是 G 的一个子图包含 G 中所有的顶点即 VV这个子图是一棵树无回路、连通因此边数恰好为 n-1n 为顶点个数生成树具有“极小连通性”去掉任意一条边树就会变成非连通图增加任意一条边就会形成回路。一个连通图的生成树可能有多个。例如一个有 4 个顶点、5 条边的图可能存在多棵不同的生成树每棵树都包含 3 条边且连接所有顶点。1.2 最小生成树的定义最小生成树就是所有生成树中边权之和最小的那一棵。如下图所示1.3 最小生成树的性质最小生成树有两个非常重要的性质也是后续算法正确性的基础切割性质设 S 是顶点集 V 的一个非空子集若边 (u,v) 是跨越 S 和 V-S 的所有边中权值最小的则 (u,v) 一定在某棵最小生成树中回路性质若边 (u,v) 是某回路中权值最大的边则 (u,v) 一定不在任何一棵最小生成树中。这两个性质看似抽象其实很容易理解切割性质告诉我们“最小的跨界边必须选”回路性质告诉我们“最大的回路边必须丢”—— 这正是贪心策略在最小生成树中的体现。1.4 最小生成树的适用场景最小生成树的核心是 “连通所有点成本最小”因此它的应用场景非常广泛通信网络搭建用最少的光纤连接所有城市保证数据互通公路建设规划在多个城镇间修建公路使总造价最低芯片布线在芯片上连接多个元件使导线总长度最短物流配送规划仓库与多个配送点的路线使运输成本最低。了解了这些基本概念后我们就可以正式进入算法的学习了。二、Prim 算法“加点法” 构建最小生成树Prim 算法是最小生成树的经典算法之一由计算机科学家 Robert C. Prim 于 1957 年提出。它的核心思路是 “从一个顶点出发逐步将距离当前树最近的顶点加入树中直到所有顶点都被加入”—— 简单来说就是 “先有一个点慢慢扩建成一棵树”。2.1 Prim 算法的基本思想Prim 算法的本质是贪心策略每一步都选择 “当前最优” 的决策最终得到全局最优解。具体步骤如下初始化选择任意一个顶点作为起始点通常选顶点 1将其加入生成树中同时维护一个 dist 数组dist [i]表示顶点 i 到当前生成树的最短距离初始时起始点的 dist 为 0其他顶点的 dist 为无穷大选最近点在所有未加入生成树的顶点中找到 dist 值最小的顶点 u将 u 加入生成树更新距离对于顶点 u 的所有邻接顶点 v若 v 未加入生成树且边 (u,v) 的权值小于dist [v]则更新dist [v] 边 (u,v) 的权值重复步骤 2-3直到所有顶点都被加入生成树共执行 n 次n 为顶点数。举个通俗的例子把生成树想象成一个 “朋友圈”起始点是你自己。每次都邀请当前和你关系最好距离最近的人加入朋友圈然后通过这个人看看他的朋友中有没有和你关系更近的更新关系后再邀请下一个人直到所有人都加入朋友圈。2.2 Prim 算法的图解过程为了让大家更直观地理解我们用一个具体的图来演示 Prim 算法的执行过程2.3 Prim 算法的代码实现邻接矩阵版Prim 算法的实现有两种常见方式邻接矩阵和邻接表。邻接矩阵适用于稠密图边数多接近 n²代码简洁直观邻接表适用于稀疏图边数少远小于 n²空间效率更高。首先给出邻接矩阵版的实现适用于 n 较小的场景比如 n≤5000#include iostream #include cstring using namespace std; const int N 5010, INF 0x3f3f3f3f; int n, m; int edges[N][N]; // 邻接矩阵存储图edges[i][j]表示i到j的边权无穷大表示无边 int dist[N]; // dist[i]表示顶点i到当前生成树的最短距离 bool st[N]; // st[i]标记顶点i是否已加入生成树 int prim() { // 初始化dist数组为无穷大 memset(dist, 0x3f, sizeof dist); dist[1] 0; // 起始点选1距离为0 int ret 0; // 存储最小生成树的权值和 // 共需要加入n个顶点循环n次 for (int i 1; i n; i) { // 步骤1找到未加入树且dist最小的顶点t int t 0; for (int j 1; j n; j) { if (!st[j] dist[j] dist[t]) { t j; } } // 如果dist[t]仍是无穷大说明图不连通无最小生成树 if (dist[t] INF) return INF; // 将t加入生成树累加权值 st[t] true; ret dist[t]; // 步骤2更新t的邻接顶点到生成树的距离 for (int j 1; j n; j) { if (!st[j] edges[t][j] dist[j]) { dist[j] edges[t][j]; } } } return ret; } int main() { cin n m; // 初始化邻接矩阵为无穷大 memset(edges, 0x3f, sizeof edges); // 自环边权值为0实际中无意义避免干扰 for (int i 1; i n; i) edges[i][i] 0; // 读入m条边无向图双向存储 for (int i 1; i m; i) { int x, y, z; cin x y z; // 处理重边保留权值最小的边 edges[x][y] edges[y][x] min(edges[x][y], z); } int res prim(); if (res INF) { cout orz endl; // 图不连通 } else { cout res endl; // 输出最小生成树的权值和 } return 0; }代码说明数据结构edges[N][N]邻接矩阵存储图的边权初始值为无穷大0x3f3f3f3f表示无边dist[N]存储每个顶点到当前生成树的最短距离st[N]标记顶点是否已加入生成树核心逻辑外层循环 n 次每次加入一个顶点内层第一个循环找 “未加入树且距离最近” 的顶点 t检查图是否连通dist [t] INF则不连通累加权值后更新 t 的邻接顶点的距离处理重边无向图中可能存在多条连接同一对顶点的边我们只保留权值最小的那条避免影响结果。2.4 Prim 算法的代码实现邻接表版当 n 较大比如 n1e5时邻接矩阵的空间复杂度 O (n²) 会超出内存限制此时需要用邻接表存储图。邻接表的空间复杂度为 O (m)m 为边数适用于稀疏图。邻接表版的实现如下#include iostream #include vector #include cstring using namespace std; typedef pairint, int PII; // first存储邻接顶点second存储边权 const int N 5010, INF 0x3f3f3f3f; int n, m; vectorPII edges[N]; // 邻接表存储图 int dist[N]; bool st[N]; int prim() { memset(dist, 0x3f, sizeof dist); dist[1] 0; int ret 0; for (int i 1; i n; i) { // 找到未加入树且dist最小的顶点t int t 0; for (int j 1; j n; j) { if (!st[j] dist[j] dist[t]) { t j; } } if (dist[t] INF) return INF; st[t] true; ret dist[t]; // 更新t的邻接顶点的距离邻接表遍历 for (auto p : edges[t]) { int v p.first; // 邻接顶点 int w p.second; // 边权 if (!st[v] w dist[v]) { dist[v] w; } } } return ret; } int main() { cin n m; for (int i 1; i m; i) { int x, y, z; cin x y z; // 无向图双向添加边 edges[x].push_back({y, z}); edges[y].push_back({x, z}); } int res prim(); if (res INF) { cout orz endl; } else { cout res endl; } return 0; }代码说明用vectorPII存储邻接表每个元素是(邻接顶点, 边权)的键值对遍历邻接顶点时直接迭代edges[t]效率比邻接矩阵更高重边的处理由于邻接表会存储所有边但在更新dist[v]时会自动选择最小的边权因此无需额外处理重边。2.5 Prim 算法的时间复杂度分析邻接矩阵版外层循环 n 次内层两个循环各 n 次总时间复杂度为 O (n²)邻接表版外层循环 n 次找最小顶点的循环 n 次更新邻接顶点的循环总次数为 O (m)每个边被遍历两次总时间复杂度为 O (n² m)。当图是稠密图m≈n²时两种版本的时间复杂度相近当图是稀疏图m≈n时邻接表版的时间复杂度接近 O (n²)但空间效率更高。如果想进一步优化时间复杂度可以使用 “堆优化” 版的 Prim 算法将 “找最小顶点” 的时间复杂度从 O (n) 降到 O (log n)整体时间复杂度优化为 O (m log n)适用于更大规模的稀疏图。不过堆优化版的代码稍复杂初学者可以先掌握基础版本后续再深入学习。三、Kruskal 算法“加边法” 构建最小生成树Kruskal 算法是另一种经典的最小生成树算法由 Joseph Kruskal 于 1956 年提出。它的核心思路与 Prim 算法完全不同先将所有边按权值排序然后依次选择权值最小的边若该边的两个顶点不在同一连通分量中则将其加入生成树直到所有顶点都连通—— 简单来说就是 “先有所有边慢慢选边拼成树”。3.1 Kruskal 算法的基本思想Kruskal 算法同样基于贪心策略但它的贪心体现在 “选边” 上每次选权值最小的边同时保证选的边不会形成回路。为了判断两个顶点是否在同一连通分量中需要用到并查集Union-Find这一数据结构 —— 并查集能高效地处理 “合并集合” 和 “查询集合根节点” 的操作是 Kruskal 算法的核心支撑。具体步骤如下初始化将所有边按权值从小到大排序初始化并查集每个顶点各自成为一个独立的集合选最小边依次从排序后的边中选择权值最小的边 (u, v)判断连通性用并查集查询 u 和 v 的根节点。若根节点不同说明 u 和 v 不在同一连通分量中则将该边加入生成树并合并 u 和 v 所在的集合若根节点相同说明加入该边会形成回路则跳过该边重复步骤 2-3直到生成树中包含 n-1 条边所有顶点连通或所有边都处理完毕。举个通俗的例子把所有边想象成 “候选公路”按造价从低到高排序。每次选造价最低的公路只要它能连接两个之前不连通的城市就修建这条公路如果它连接的是已经连通的城市就放弃这条公路直到所有城市都连通。3.2 Kruskal 算法的图解过程3.3 Kruskal 算法的代码实现并查集 排序Kruskal 算法的代码核心是“边排序”和“并查集操作”实现如下#include iostream #include algorithm using namespace std; const int N 5010, M 2e5 10, INF 0x3f3f3f3f; int n, m; // 存储边x和y是顶点z是边权 struct Edge { int x, y, z; } edges[M]; // 并查集数组parent[i]表示顶点i的父节点 int parent[N]; // 比较函数按边权从小到大排序 bool cmp(Edge a, Edge b) { return a.z b.z; } // 并查集查询操作路径压缩 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } int kruskal() { // 初始化并查集 for (int i 1; i n; i) { parent[i] i; } // 对边按权值排序 sort(edges 1, edges 1 m, cmp); int cnt 0; // 生成树中已选的边数 int ret 0; // 最小生成树的权值和 for (int i 1; i m; i) { int x edges[i].x; int y edges[i].y; int z edges[i].z; // 查询x和y的根节点 int fx find(x); int fy find(y); // 若根节点不同说明不连通加入该边 if (fx ! fy) { parent[fx] fy; // 合并集合 cnt; ret z; // 当边数达到n-1时说明所有顶点已连通直接返回 if (cnt n - 1) { break; } } } // 若边数不足n-1说明图不连通 return cnt n - 1 ? ret : INF; } int main() { cin n m; // 读入m条边 for (int i 1; i m; i) { cin edges[i].x edges[i].y edges[i].z; } int res kruskal(); if (res INF) { cout orz endl; } else { cout res endl; } return 0; }代码说明数据结构Edge结构体存储每条边的两个顶点和权值parent[N]并查集的父节点数组核心逻辑并查集初始化每个顶点的父节点是自己边排序按权值从小到大排序保证每次选最小边并查集查询用路径压缩优化提高查询效率合并集合若两个顶点不连通合并它们的集合并累加边权终止条件当生成树的边数达到 n-1 时直接返回结果无需继续处理后续边提高效率。3.4 Kruskal 算法的时间复杂度分析Kruskal 算法的时间复杂度主要由两部分构成边排序时间复杂度为 O (m log m)m 为边数并查集操作每次查询和合并的时间复杂度接近 O (1)路径压缩和按秩合并优化后总共有 m 次操作时间复杂度为 O (m α(n))α 是阿克曼函数的反函数增长极慢可视为常数因此Kruskal 算法的总时间复杂度为 O (m log m)这使得它非常适合稀疏图m 较小—— 当 m 远小于 n² 时Kruskal 算法的效率远高于 Prim 算法的 O (n²) 版本。3.5 并查集的优化路径压缩 按秩合并在上面的代码中我们只使用了 “路径压缩” 优化并查集的查询操作。为了进一步提高效率还可以加入 “按秩合并” 优化 —— 合并两个集合时将秩树的高度较小的集合合并到秩较大的集合中避免树的高度过高从而优化查询效率。优化后的并查集实现如下// 并查集数组parent[i]表示父节点rank[i]表示树的秩高度 int parent[N], rank[N]; // 初始化并查集 void init() { for (int i 1; i n; i) { parent[i] i; rank[i] 1; // 初始时每个树的秩为1 } } // 查询操作路径压缩 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } // 合并操作按秩合并 void unite(int x, int y) { int fx find(x); int fy find(y); if (fx fy) return; // 将秩小的树合并到秩大的树中 if (rank[fx] rank[fy]) { parent[fx] fy; } else { parent[fy] fx; // 若秩相等合并后秩1 if (rank[fx] rank[fy]) { rank[fx]; } } }将 Kruskal 算法中的并查集部分替换为上述代码可进一步提高算法效率尤其是在顶点数较多的场景下。四、Prim 算法与 Kruskal 算法的对比该选哪一个通过前面的学习我们已经掌握了两种最小生成树算法的实现。那么在实际应用中该如何选择合适的算法呢下面从多个维度进行对比对比维度Prim 算法Kruskal 算法核心思想加点法从顶点出发逐步扩展生成树加边法从边出发逐步选择有效边数据结构依赖邻接矩阵 / 邻接表并查集 边排序时间复杂度基础版 O (n²)堆优化版 O (m log n)O(m log m)空间复杂度邻接矩阵 O (n²)邻接表 O (nm)O (m)存储边 O (n)并查集适用场景稠密图m≈n²稀疏图m≈n处理带权图支持非负权边支持非负权边处理图不连通可检测返回 INF可检测边数不足 n-1选择建议如果是稠密图比如 n1000m1e6优先选择 Prim 算法的邻接矩阵版代码简洁效率稳定如果是稀疏图比如 n1e5m1e5优先选择 Kruskal 算法时间复杂度 O (m log m)空间效率更高如果顶点数较少n≤1000两种算法都可以可根据个人习惯选择如果需要处理更大规模的稀疏图可选择堆优化版的 Prim 算法或优化后的 Kruskal 算法。五、经典例题实战从模板到应用理论学习之后必须通过实战巩固。下面为大家精选了两道洛谷上的经典例题涵盖模板题、应用场景题、变形题帮助大家灵活运用两种算法。例题 1买礼物洛谷 P1194题目链接https://www.luogu.com.cn/problem/P1194题目描述明明想要买 B 样东西每样东西价格都是 A 元。商店有促销活动如果买了第 I 样东西再买第 J 样那么就可以只花 K_{I,J} 元K_{I,J}K_{J,I}。若 K_{I,J}0则无优惠。求明明最少要花多少钱。输入格式第一行两个整数 A、B。接下来 B 行每行 B 个数第 I 行第 J 个为 K_{I,J}。输出格式一个整数为最小要花的钱数。示例输入 23 3 0 2 4 2 0 2 4 2 0示例输出 27解法分析这道题的关键是将问题转化为最小生成树问题每个礼物看作一个顶点共 B 个顶点优惠活动 K_{I,J} 看作连接顶点 I 和 J 的边边权为 K_{I,J}若不使用优惠买第 I 样东西的成本是 A 元相当于每个顶点有一条 “自环边”或连接到一个虚拟顶点的边边权为 A最终问题转化为选择一些边使得所有顶点都被覆盖即买所有礼物且边权之和最小。这里有两种选择直接买某样礼物花费 A 元相当于选 “自环边”先买另一样礼物再用优惠买该礼物花费 K_{I,J} 元相当于选连接 I 和 J 的边因此我们可以构建一个包含 B 个顶点的图边包括所有有效的 K_{I,J}K_{I,J}≠0 且 K_{I,J}A然后求最小生成树。生成树的边权之和加上未被覆盖的顶点的 A 元实际上生成树包含所有顶点因此无需额外加就是最小总花费。代码实现#include iostream #include algorithm using namespace std; const int N 500 * 500 10; int A, B; struct Edge { int x, y, z; } edges[N]; int parent[N]; int pos 0; // 边的计数器 bool cmp(Edge a, Edge b) { return a.z b.z; } int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } int main() { cin A B; // 读入优惠边K_ij≠0且K_ijA且ij避免重复 for (int i 1; i B; i) { for (int j 1; j B; j) { int k; cin k; if (i j || k 0 || k A) continue; edges[pos] {i, j, k}; } } // 初始化并查集 for (int i 1; i B; i) parent[i] i; // Kruskal算法选边 sort(edges 1, edges 1 pos, cmp); int cnt 0, res 0; for (int i 1; i pos; i) { int x edges[i].x, y edges[i].y, z edges[i].z; int fx find(x), fy find(y); if (fx ! fy) { parent[fx] fy; cnt; res z; } } // 总花费 生成树边权和 未被优惠覆盖的顶点数 * A // 未被优惠覆盖的顶点数 B - cnt生成树有cnt条边覆盖cnt1个顶点不生成树有B个顶点cntB-1时覆盖所有 // 实际上每个顶点要么通过优惠边连接计入res要么直接购买花费A因此总花费res (B - cnt) * A cout res (B - cnt) * A endl; return 0; }例题 2滑雪洛谷 P2573题目链接https://www.luogu.com.cn/problem/P2573题目描述雪山有 n 个景点顶点m 条轨道边每个景点有高度 h_i。可以从景点 i 滑到 j 当且仅当 h_i ≥ h_j。可以使用时间胶囊回溯到之前的景点。求最多能到达多少个景点以及此时的最短滑行距离总和。输入格式第一行 n、m第二行 n 个整数 h_i接下来 m 行 u、v、k表示景点 u 和 v 之间有一条长度为 k 的轨道。输出格式最多能到达的景点数和最短滑行距离总和。示例输入3 3 3 2 1 1 2 1 2 3 1 1 3 10示例输出3 2解法分析这道题是最小生成树的变形需要结合 DFS 和 Kruskal 算法最多能到达的景点数从起点 1 出发通过 DFS/BFS 遍历所有可达的景点h_i ≥ h_j统计个数最短滑行距离总和由于可以回溯相当于需要选择一些边将所有可达的景点连接起来且边权之和最小即最小生成树。但由于滑行方向限制h_i ≥ h_j排序时需优先选择高度高的顶点的边确保能向下滑行。代码实现#include iostream #include algorithm #include cstring #include vector using namespace std; typedef long long LL; typedef pairint, int PII; const int N 1e5 10, M 2e6 10; int n, m; int h[N]; // 每个景点的高度 vectorPII edges[N]; // 存储图 bool st[N]; // 标记是否已遍历DFS用 int cnt 0; // 最多能到达的景点数 // 存储用于Kruskal的边 struct Edge { int x, y, z; } e[M]; int pos 0; // 边的计数器 int parent[N]; // DFS遍历所有可达的景点 void dfs(int u) { cnt; st[u] true; for (auto p : edges[u]) { int v p.first, k p.second; // 记录边用于后续Kruskal e[pos] {u, v, k}; if (!st[v] h[u] h[v]) { dfs(v); } } } // 边排序优先按邻接顶点的高度降序再按边权升序 bool cmp(Edge a, Edge b) { if (h[a.y] ! h[b.y]) return h[a.y] h[b.y]; return a.z b.z; } int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } // Kruskal算法求最小生成树的边权和 LL kruskal() { for (int i 1; i n; i) parent[i] i; sort(e 1, e 1 pos, cmp); LL res 0; for (int i 1; i pos; i) { int x e[i].x, y e[i].y, z e[i].z; // 只考虑可达的景点 if (!st[x] || !st[y]) continue; int fx find(x), fy find(y); if (fx ! fy) { parent[fx] fy; res z; } } return res; } int main() { cin n m; for (int i 1; i n; i) cin h[i]; for (int i 1; i m; i) { int x, y, z; cin x y z; // 双向存储边因为可能从y滑到x只要h[y]h[x] if (h[x] h[y]) edges[x].push_back({y, z}); if (h[y] h[x]) edges[y].push_back({x, z}); } // 从景点1出发DFS dfs(1); // Kruskal求最短滑行距离 LL dist_sum kruskal(); cout cnt dist_sum endl; return 0; }总结最小生成树是图论中的基础算法也是面试和算法竞赛中的高频考点。希望本文能帮助你彻底掌握这一知识点在后续的学习和实践中灵活运用。如果有任何疑问或建议欢迎在评论区留言讨论