当前位置：首页 > article >正文

c/c++蓝桥杯经典编程题100道（23）最小生成树

article 2025/2/21 14:27:34

最小生成树（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 100

typedef 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); // 输出 19
    return 0;
}

代码逻辑：

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

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

通俗解释：

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

#include <stdio.h>
#include <limits.h>

#define V 5

int 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); // 总权重=16
    return 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); // 总权重=16
    return 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; // 输出19
    return 0;
}

代码逻辑：