最小生成树

一、引入

最小生成树是一个连接图中所有节点的子图，并使得其边的权重和最小。

本文介绍两种算法，kruskal 算法以及 prim算法

二、Kruskal

1.Kruskal算法简介

Kruskal算法是一种用于求解**加权无向图最小生成树（Minimum Spanning Tree, MST）**的贪心算法。Kruskal算法通过对所有边进行排序并逐步添加到生成树中的方法来构造最小生成树。

2.Kruskal算法的基本原理

Kruskal算法的基本思想是：在不构成环的前提下，按照边权重从小到大的顺序，逐步将边加入到生成树中。为实现这一点，Kruskal算法使用了并查集数据结构，以检测是否会形成环。

3.Kruskal算法的主要步骤

1. 初始化：初始化并查集。
2. 边排序：将所有边按照权重从小到大排序。
3. 逐边添加：从权重最小的边开始，依次检查每条边连接的顶点是否属于同一集合（即是否构成环）：
   • 如果边的两个顶点不在同一集合，则将该边加入到最小生成树，并合并顶点所在的集合。
   • 如果边的两个顶点已在同一集合，则跳过该边。
4. 结束条件：当生成树中的边数为n-1（n为顶点数）时，算法结束。

Kruskal算法的时间复杂度主要取决于排序的复杂度，即O(E log E)，其中E为边的数量。

4.代码实现（关键部分）

// Kruskal算法实现
int kruskal(int n, vector<Edge>& edges) {
    // 对边按照权重从小到大排序
    sort(edges.begin(), edges.end());

    initUnionFind(n); // 初始化并查集
    int mst_weight = 0;
    int edge_count = 0;

    for (const auto& edge : edges) {
        // 检查边的两个顶点是否属于不同集合
        if (unionSets(edge.u, edge.v)) {
            mst_weight += edge.w;
            edge_count++;
            cout << "Edge (" << edge.u << ", " << edge.v << ") with weight " << edge.w << " added to MST." << endl;
            // 如果已经有n-1条边，生成树构建完成
            if (edge_count == n - 1) {
                break;
            }
        }
    }
    // 如果生成树包含的边数不足n-1，说明图不连通
    if (edge_count != n - 1) {
        cout << "The graph is not connected!" << endl;
        return -1;
    }
    return mst_weight;
}

三、Prim

1. Prim算法简介

Prim算法是一种用于求解**加权无向连通图的最小生成树（Minimum Spanning Tree, MST）**的贪心算法。Prim算法从一个起始节点出发，通过不断加入与已生成部分连接且权值最小的边，逐步扩大树，直至包含所有节点。

2. Prim算法的基本原理

Prim算法的核心思想是“从一个顶点出发，不断向树中添加距离当前生成树最近的节点”，具体过程如下：

1. 从图中的某一个起始节点开始，初始化为最小生成树的第一个节点。

2. 找出图中连接生成树中的节点与树外节点的边中权值最小的边，并将边所连接的节点加入生成树。

3. 重复步骤2，直到所有节点都被包含在树中。

   

3. Prim算法的主要步骤

1. 选择一个起始节点，将其标记为已访问，将与该节点直接连接的边存入最小堆（优先队列）。
2. 从最小堆中取出权值最小的边，如果边连接的另一端节点未被访问，则将此节点加入生成树，并将与此节点相连的所有边加入最小堆。
3. 重复步骤2，直到所有节点都被访问。

5. 代码实现（关键部分）

typedef pair<int, int> Edge; // first为边权值，second为节点编号
const int MAX_V = 100; // 假设图最多有100个节点
vector<Edge> adj[MAX_V]; // 邻接表
bool inMST[MAX_V];       // 标记节点是否已在生成树中
int key[MAX_V];          // 记录每个节点到生成树的最小边权
int parent[MAX_V];       // 记录生成树中的连接边

void primMST(int V) {
    fill(inMST, inMST + V, false);
    fill(key, key + V, INT_MAX);
    fill(parent, parent + V, -1);

    priority_queue<Edge, vector<Edge>, greater<Edge>> pq; // 小顶堆，优先队列

    int start = 0; // 从节点0开始
    pq.push({0, start});
    key[start] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (inMST[u]) continue; // 如果节点已经在生成树中，跳过
        inMST[u] = true;

        // 更新与节点u相邻的节点的边
        for (auto& [weight, v] : adj[u]) {
            if (!inMST[v] && weight < key[v]) {
                key[v] = weight;
                pq.push({key[v], v});
                parent[v] = u;
            }
        }
    }
}