株洲发布信息网_seo网站关键词优化报价_网站设计制作在哪能看_企业宣传推广怎么做

最小生成树（MST）问题

->返回c/c++蓝桥杯经典编程题100道-目录

最小生成树（MST）问题

一、题型解释

二、例题问题描述

三、C语言实现

解法1：Kruskal算法（基于并查集，难度★★★）

解法2：Prim算法（邻接矩阵，难度★★）

四、C++实现

解法1：Prim算法（优先队列优化，难度★★☆）

解法2：Kruskal算法（STL优化，难度★★★）

五、总结对比表

六、特殊方法与内置函数补充

1. C语言 qsort

2. C++ STL sort

3. 优先队列（priority_queue）

一、题型解释

最小生成树是连接图中所有顶点的边构成的树，且所有边的权重和最小。常见题型：

基础MST：求连通图的最小生成树总权重（如Kruskal、Prim算法）。
变种问题：
- 判断图是否连通（不连通则无MST）。
- 次小生成树（权值和第二小的生成树）。
- 特定约束（如必须包含某条边）。

二、例题问题描述

例题1：输入图的边集合，输出最小生成树的总权重。
例题2：输入非连通图，输出“图不连通”。
例题3：输入带权图，输出必须包含边 (A,B) 的最小生成树权重。

三、C语言实现

解法1：Kruskal算法（基于并查集，难度★★★）

通俗解释：

贪心策略：按边权重从小到大选择，确保不形成环。
核心操作：并查集（Union-Find）判断两个顶点是否连通。

#include <stdio.h>
#include <stdlib.h>#define MAX_EDGES 100
#define MAX_VERTICES 100typedef struct {int src, dest, weight;
} Edge;typedef struct {int parent[MAX_VERTICES];int rank[MAX_VERTICES];
} UnionFind;// 并查集初始化
void initUF(UnionFind *uf, int vertices) {for (int i = 0; i < vertices; i++) {uf->parent[i] = i;uf->rank[i] = 0;}
}// 查找根节点（路径压缩）
int find(UnionFind *uf, int x) {if (uf->parent[x] != x)uf->parent[x] = find(uf, uf->parent[x]); // 路径压缩return uf->parent[x];
}// 合并两个集合（按秩合并）
void unite(UnionFind *uf, int x, int y) {int xRoot = find(uf, x);int yRoot = find(uf, y);if (xRoot == yRoot) return;if (uf->rank[xRoot] < uf->rank[yRoot])uf->parent[xRoot] = yRoot;else {uf->parent[yRoot] = xRoot;if (uf->rank[xRoot] == uf->rank[yRoot])uf->rank[xRoot]++;}
}// 边按权重排序（升序）
int compareEdges(const void *a, const void *b) {return ((Edge*)a)->weight - ((Edge*)b)->weight;
}int kruskalMST(Edge edges[], int edgeCount, int vertices) {qsort(edges, edgeCount, sizeof(Edge), compareEdges); // 按权重排序UnionFind uf;initUF(&uf, vertices);int totalWeight = 0, selectedEdges = 0;for (int i = 0; i < edgeCount && selectedEdges < vertices - 1; i++) {Edge e = edges[i];int rootSrc = find(&uf, e.src);int rootDest = find(&uf, e.dest);if (rootSrc != rootDest) { // 不形成环unite(&uf, rootSrc, rootDest);totalWeight += e.weight;selectedEdges++;}}if (selectedEdges != vertices - 1) {printf("图不连通！\n");return -1;}return totalWeight;
}int main() {Edge edges[] = {{0,1,10}, {0,2,6}, {0,3,5}, {1,3,15}, {2,3,4}};int edgeCount = 5, vertices = 4;int result = kruskalMST(edges, edgeCount, vertices);if (result != -1)printf("最小生成树权重：%d\n", result); // 输出 19return 0;
}

代码逻辑：

并查集初始化：每个节点初始父节点为自身。
边排序：按权重从小到大排序。
选边建树：依次选择边，若两端点不在同一集合则合并，累加权重。
连通性检查：若最终边数不足 V-1，说明图不连通。

解法2：Prim算法（邻接矩阵，难度★★）

通俗解释：

贪心策略：从任意顶点开始，逐步扩展最小边连接未访问顶点。
核心操作：维护候选边的最小权重。

#include <stdio.h>
#include <limits.h>#define V 5int minKey(int key[], int visited[]) {int min = INT_MAX, min_index;for (int v = 0; v < V; v++)if (!visited[v] && key[v] < min)min = key[v], min_index = v;return min_index;
}void primMST(int graph[V][V]) {int parent[V];    // 存储生成树结构int key[V];       // 记录顶点到生成树的最小边权重int visited[V];   // 标记顶点是否加入生成树for (int i = 0; i < V; i++)key[i] = INT_MAX, visited[i] = 0;key[0] = 0;       // 选择顶点0作为起点parent[0] = -1;   // 根节点无父节点for (int count = 0; count < V - 1; count++) {int u = minKey(key, visited); // 选取最小key的顶点visited[u] = 1;// 更新相邻顶点的key值for (int v = 0; v < V; v++)if (graph[u][v] && !visited[v] && graph[u][v] < key[v])parent[v] = u, key[v] = graph[u][v];}// 输出结果printf("边\t权重\n");for (int i = 1; i < V; i++)printf("%d-%d\t%d\n", parent[i], i, graph[i][parent[i]]);
}int main() {int graph[V][V] = {{0, 2, 0, 6, 0},{2, 0, 3, 8, 5},{0, 3, 0, 0, 7},{6, 8, 0, 0, 9},{0, 5, 7, 9, 0}};primMST(graph); // 总权重=16return 0;
}

代码逻辑：

初始化：key数组记录各顶点到生成树的最小边权重，起点设为0。
循环扩展：每次选择key最小的顶点加入生成树，更新其邻居的key值。
输出结构：parent数组记录生成树的边。

四、C++实现

解法1：Prim算法（优先队列优化，难度★★☆）

通俗解释：

使用优先队列快速获取最小权重边，时间复杂度优化至O(E + V log V)。

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;typedef pair<int, int> pii; // {权重, 顶点}void primMST(vector<vector<pii>>& graph, int V) {vector<int> key(V, INT_MAX);vector<bool> visited(V, false);vector<int> parent(V, -1);priority_queue<pii, vector<pii>, greater<pii>> pq;key[0] = 0;pq.push({0, 0});while (!pq.empty()) {int u = pq.top().second;pq.pop();if (visited[u]) continue;visited[u] = true;for (auto &neighbor : graph[u]) {int v = neighbor.first;int weight = neighbor.second;if (!visited[v] && weight < key[v]) {parent[v] = u;key[v] = weight;pq.push({key[v], v});}}}cout << "边\t权重" << endl;for (int i = 1; i < V; i++)cout << parent[i] << "-" << i << "\t" << key[i] << endl;
}int main() {int V = 5;vector<vector<pii>> graph(V);graph[0].push_back({1, 2});graph[0].push_back({3, 6});graph[1].push_back({0, 2});graph[1].push_back({2, 3});graph[1].push_back({4, 5});graph[2].push_back({1, 3});graph[2].push_back({4, 7});graph[3].push_back({0, 6});graph[3].push_back({4, 9});graph[4].push_back({1, 5});graph[4].push_back({2, 7});graph[4].push_back({3, 9});primMST(graph, V); // 总权重=16return 0;
}

代码逻辑：

优先队列：存储{权重, 顶点}，自动按权重排序。
懒惰删除：跳过已处理的顶点。
邻接表：使用vector存储图的邻接关系。

解法2：Kruskal算法（STL优化，难度★★★）

通俗解释：

利用STL的排序和并查集库简化实现。

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;struct Edge {int src, dest, weight;bool operator<(const Edge &other) const {return weight < other.weight;}
};struct UnionFind {vector<int> parent, rank;UnionFind(int n) : parent(n), rank(n, 0) {for (int i = 0; i < n; i++)parent[i] = i;}int find(int x) {if (parent[x] != x)parent[x] = find(parent[x]); // 路径压缩return parent[x];}void unite(int x, int y) {int xRoot = find(x), yRoot = find(y);if (xRoot == yRoot) return;if (rank[xRoot] < rank[yRoot])parent[xRoot] = yRoot;else {parent[yRoot] = xRoot;if (rank[xRoot] == rank[yRoot])rank[xRoot]++;}}
};int kruskalMST(vector<Edge>& edges, int V) {sort(edges.begin(), edges.end());UnionFind uf(V);int totalWeight = 0, selectedEdges = 0;for (Edge &e : edges) {if (selectedEdges == V - 1) break;int rootSrc = uf.find(e.src);int rootDest = uf.find(e.dest);if (rootSrc != rootDest) {uf.unite(rootSrc, rootDest);totalWeight += e.weight;selectedEdges++;}}if (selectedEdges != V - 1) {cout << "图不连通！" << endl;return -1;}return totalWeight;
}int main() {vector<Edge> edges = {{0,1,10}, {0,2,6}, {0,3,5}, {1,3,15}, {2,3,4}};int V = 4;int result = kruskalMST(edges, V);if (result != -1)cout << "最小生成树权重：" << result << endl; // 输出19return 0;
}

代码逻辑：