最小生成树构建的C++实现代码示例

在计算机科学中，最小生成树（Minimum Spanning Tree, MST）是一种用于解决图论问题的重要工具。最小生成树是指在一个加权连通图中寻找一颗连接所有顶点且总权重最小的生成树。本文将通过一个具体实例介绍如何使用Prim算法来构建最小生成树，并提供相应的C++代码实现。

1. 最小生成树及其应用

最小生成树在实际问题中有广泛的应用，例如网络设计、路由选择等场景中都能见到其身影。给定一张加权图，寻找连接所有顶点的最经济方案是这类问题的常见要求。

2. Prim算法简介

Prim算法是一种经典算法，用于解决无向图的最小生成树问题。该算法起始于任意一个顶点，逐步选择当前已经加入集合中的顶点与未加入集合中顶点之间的最小权值边，直到所有的顶点都加入到生成树中。

3. C++代码实现

下面是一个使用Prim算法构建最小生成树的C++代码示例。这里我们用邻接矩阵来表示图，并采用优先队列存储当前未被访问的最小权重边。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 用于存放图结构，以及记录每个顶点的状态（是否已经加入生成树）
struct Graph {
    int V; // 顶点数量
    vector<vector<int>> adj; // 邻接矩阵表示的图

    Graph(int v) : V(v), adj(v, vector<int>(v, INT_MAX)) {}

    void addEdge(int u, int v, int weight);
};

void Graph::addEdge(int u, int v, int weight) {
    adj[u][v] = weight;
    adj[v][u] = weight; // 无向图
}

struct EdgeInfo { 
    int vertex; // 边的另一个端点
    int weight; // 边的权重

    bool operator<(const EdgeInfo& e2) const {
        return weight > e2.weight;
    }
};

void primMST(Graph &graph, vector<int> &parent, vector<bool> &key);

int main() {
    int V = 5; // 顶点数
    Graph graph(V);
    
    // 添加边及其权重
    graph.addEdge(0, 1, 28);
    graph.addEdge(0, 3, 16);
    graph.addEdge(1, 3, 12);
    graph.addEdge(1, 2, 18);
    graph.addEdge(1, 4, 22);
    graph.addEdge(2, 4, 25);
    graph.addEdge(3, 4, 19);

    vector<int> parent(V); // 记录生成树中每条边的父节点
    vector<bool> key(V, false); // 标记顶点是否已加入生成树

    primMST(graph, parent, key);

    cout << "最小生成树的权重为: " << -1 * key[0] << endl;

    return 0;
}

void primMST(Graph &graph, vector<int> &parent, vector<bool> &key) {
    priority_queue<EdgeInfo> pq; // 小顶堆，用于存储待处理边
    int u = 0; // 从顶点0开始

    key[u] = true;

    for (int v = 1; v < graph.V; ++v) {
        parent[v] = u;
        key[v] = false;
        pq.push({v, graph.adj[u][v]});
    }

    while (!pq.empty()) {
        EdgeInfo minEdge = pq.top(); // 取出当前最小权重的边
        int v = minEdge.vertex;

        if (key[v]) continue; // 如果顶点已经加入生成树，跳过

        cout << "边 (" << parent[v] << ", " << v << ") 的权重为: " << -1 * pq.top().weight << endl;
        key[v] = true;

        for (int w = 0; w < graph.V; ++w) {
            if (!key[w] && graph.adj[v][w]) { // 检查与当前顶点相邻且未加入生成树的顶点
                pq.push({w, graph.adj[v][w]});
            }
        }

        pq.pop(); // 当前边已处理完毕，从堆中移除
    }
}

4. 解释

这段代码首先定义了一个Graph类来表示图，并且包含添加边的方法。primMST函数实现Prim算法的核心逻辑：使用优先队列存储当前最小的边，并逐步构建生成树。

主要步骤：

初始化：设定起始顶点，将所有顶点加入未访问集合。
初始化优先队列：为每个顶点设置初始权重（在图中不存在的情况下设置为INT_MAX）并放入优先队列。
循环选择最小边：从优先队列取出当前最短的边。若该边对应的一个端点尚未加入生成树，则将其加入，并更新另一个端点的邻居信息。

通过上述步骤，可以逐步构建出图的最小生成树，并计算其总权重。

这段代码可以根据需要调整顶点数量和添加不同的边及其权重值来进行测试。