最小生成树模板

<think>好的，我现在需要为用户介绍最小生成树模板。首先，我得回忆一下最小生成树的基本概念和相关算法。最小生成树（Minimum Spanning Tree，MST）是在一个加权无向图中找到一棵包含所有顶点的树，并且边的权值之和最小。常用的算法有Prim算法和Kruskal算法。 接下来，我需要确定用户的需求是什么。他们可能是在准备算法竞赛或者学习图论，需要模板代码来实现这两种算法。因此，我应该分别解释这两种算法的原理，然后给出代码模板，并比较它们的适用场景。 对于Kruskal算法，核心是使用并查集来管理连通性，按边的权重从小到大排序，依次选择不形成环的边。这里要注意路径压缩和按秩合并优化并查集的操作，以提高效率。代码部分需要结构体或类来存储边，以及并查集的实现。时间复杂度方面，Kruskal是O(M log M)，适合边较少的稀疏图。 然后是Prim算法，这通常使用优先队列（堆）来实现，类似于Dijkstra算法。需要维护一个最小堆来选择当前权值最小的边，同时记录哪些顶点已加入生成树。Prim算法的时间复杂度取决于使用邻接矩阵还是邻接表，以及是否用堆优化。使用堆优化的版本是O(M log N)，适合边较多的稠密图。 在编写代码模板时，要确保语法正确，变量命名清晰，并加上必要的注释。例如，在Kruskal的模板中，需要初始化并查集，排序边，然后遍历合并；在Prim的模板中，则需要构建邻接表，使用优先队列，并维护一个visited数组。 同时，应该指出两种算法的区别：Kruskal更适合稀疏图，而Prim在稠密图中表现更好。这是因为Kruskal的时间复杂度主要取决于边的数量，而Prim在邻接矩阵的情况下是O(N²)，对于稠密图来说可能更快，但堆优化后更适合边多的情况。 可能用户会混淆这两种算法的应用场景，所以需要明确说明。另外，示例输入输出可以帮助用户理解模板的使用方法，比如给出一个具体的图结构，展示算法如何逐步构建最小生成树。 最后，需要检查是否有遗漏的细节，比如处理图不连通的情况（此时无法生成MST），或者在代码中处理可能的异常。确保提供的模板代码能够正确处理各种情况，比如边权为负数时是否影响算法逻辑（不影响，因为MST允许负权边，只要总权最小）。 总结起来，我需要分步骤介绍两种算法，提供清晰的代码模板，并比较它们的优缺点和使用场景，帮助用户根据具体问题选择合适的算法。</think>最小生成树（Minimum Spanning Tree, MST）是连接加权无向图所有顶点的边权总和最小的树。以下是两种常用算法的模板及解析： --- ### 一、Kruskal 算法（贪心+并查集） **适用场景**：稀疏图（边少） **时间复杂度**：O(M log M) （M为边数） #### 算法步骤： 1. 将边按权值升序排序 2. 初始化并查集 3. 遍历所有边，用并查集判断是否形成环 4. 累计不形成环的边权 ```cpp #include <vector> #include <algorithm> using namespace std; struct Edge { int u, v, w; Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {} }; vector<Edge> edges; int parent[1005]; int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } bool unite(int x, int y) { x = find(x), y = find(y); if (x == y) return false; parent[y] = x; return true; } int kruskal(int n) { // n为顶点数 sort(edges.begin(), edges.end(), [](Edge& a, Edge& b) { return a.w < b.w; }); for (int i = 1; i <= n; ++i) parent[i] = i; int sum = 0, cnt = 0; for (auto& e : edges) { if (unite(e.u, e.v)) { sum += e.w; if (++cnt == n-1) break; // 选够n-1条边 } } return cnt == n-1 ? sum : -1; // -1表示图不连通 } ``` --- ### 二、Prim 算法（优先队列） **适用场景**：稠密图（边多） **时间复杂度**：O(M log N) （N为顶点数） #### 算法步骤： 1. 任选起始点，初始化优先队列 2. 每次取出离当前树最近的顶点 3. 更新相邻顶点到树的距离 ```cpp #include <vector> #include <queue> #include <climits> using namespace std; typedef pair<int, int> pii; // {weight, vertex} int prim(vector<vector<pii>>& graph, int n) { vector<bool> vis(n+1, false); priority_queue<pii, vector<pii>, greater<pii>> pq; int sum = 0, cnt = 0; pq.push({0, 1}); // 从顶点1开始 while (!pq.empty()) { auto [w, u] = pq.top(); pq.pop(); if (vis[u]) continue; vis[u] = true; sum += w; cnt++; for (auto& [v, cost] : graph[u]) { if (!vis[v]) { pq.push({cost, v}); } } } return cnt == n ? sum : -1; // -1表示图不连通 } ``` --- ### 三、算法对比 | 特性 | Kruskal | Prim | |-------------|-----------------------------|--------------------| | 数据结构 | 并查集 + 排序 | 优先队列 | | 适用场景 | 稀疏图（边少） | 稠密图（边多） | | 时间复杂度 | O(M log M) | O(M log N) | | 是否需要邻接表 | 不需要 | 需要 | --- ### 四、使用示例 输入（邻接表）： ``` 顶点数n=3，边： 1-2 (权重5) 2-3 (权重6) 1-3 (权重4) ``` 输出： ``` 最小生成树权值和 = 5 + 4 = 9 ``` --- 根据图的稠密程度选择算法：稀疏图优先用Kruskal，邻接矩阵存储的稠密图可用朴素版Prim（时间复杂度O(N²)）。模板代码需根据具体题目调整顶点编号方式（0-based或1-based）。