Leetcode记录：最小生成树

31 Aug 2024

prim算法

prim算法是从节点的角度采用贪心的策略每次寻找距离最小生成树最近的节点并加入到最小生成树中。其算法核心就是三步：

选距离生成树最近节点
最近节点加入生成树
更新非生成树节点到生成树的距离（即更新minDist数组）

时间复杂度为O(n^2), n为节点数量。

int main() {
    int v, e;
    int x, y, k;
    cin >> v >> e;
    // 填一个默认最大值，题目描述val最大为10000
    vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));
    while (e--) {
        cin >> x >> y >> k;
        // 因为是双向图，所以两个方向都要填上
        grid[x][y] = k;
        grid[y][x] = k;

    }
    // 所有节点到最小生成树的最小距离
    vector<int> minDist(v + 1, 10001);

    // 这个节点是否在树里
    vector<bool> isInTree(v + 1, false);

     //加上初始化
    vector<int> parent(v + 1, -1);

    // 我们只需要循环 n-1次，建立 n - 1条边，就可以把n个节点的图连在一起
    for (int i = 1; i < v; i++) {

        // 1、prim三部曲，第一步：选距离生成树最近节点
        int cur = -1; // 选中哪个节点 加入最小生成树
        int minVal = INT_MAX;
        for (int j = 1; j <= v; j++) { // 1 - v，顶点编号，这里下标从1开始
            //  选取最小生成树节点的条件：
            //  （1）不在最小生成树里
            //  （2）距离最小生成树最近的节点
            if (!isInTree[j] &&  minDist[j] < minVal) {
                minVal = minDist[j];
                cur = j;
            }
        }
        // 2、prim三部曲，第二步：最近节点（cur）加入生成树
        isInTree[cur] = true;

        // 3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）
        // cur节点加入之后， 最小生成树加入了新的节点，那么所有节点到 最小生成树的距离（即minDist数组）需要更新一下
        // 由于cur节点是新加入到最小生成树，那么只需要关心与 cur 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢
        for (int j = 1; j <= v; j++) {
            // 更新的条件：
            // （1）节点是 非生成树里的节点
            // （2）与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小
            // 很多录友看到自己 就想不明白什么意思，其实就是 cur 是新加入 最小生成树的节点，那么 所有非生成树的节点距离生成树节点的最近距离 由于 cur的新加入，需要更新一下数据了
            if (!isInTree[j] && grid[cur][j] < minDist[j]) {
                minDist[j] = grid[cur][j];
                parent[j] = cur; // 记录边
            }
        }
    }
    // 统计结果，minDist[i]均为最小生成树的一条边的权值
    int result = 0;
    for (int i = 2; i <= v; i++) { // 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1条边
        result += minDist[i];
    }
}

Kruskal算法

prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。 Kruskal的思路：

边的权值排序，因为要优先选最小的边加入到生成树里
遍历排序后的边
1. 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
2. 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合

但在代码中，如果将两个节点加入同一个集合，又如何判断两个节点是否在同一个集合呢？这里就涉及到并查集。

struct Edge {
    int l, r, val;
};

int n = 10001;

vector<int> father(n, -1); 

void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}

int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); 
}

void join(int u, int v) {
    u = find(u); 
    v = find(v); 
    if (u == v) return ; 
    father[v] = u;
}

int main() {

    int v, e;
    int v1, v2, val;
    vector<Edge> edges;
    int result_val = 0;
    cin >> v >> e;
    while (e--) {
        cin >> v1 >> v2 >> val;
        edges.push_back({v1, v2, val});
    }

    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
            return a.val < b.val;
    });

    vector<Edge> result; // 存储最小生成树的边

    init();

    for (Edge edge : edges) {

        int x = find(edge.l);
        int y = find(edge.r);


        if (x != y) {
            result.push_back(edge); // 保存最小生成树的边
            result_val += edge.val; 
            join(x, y);
        }
    }

    // 打印最小生成树的边
    for (Edge edge : result) {
        cout << edge.l << " - " << edge.r << " : " << edge.val << endl;
    }

    return 0;
}

Kruskal 与 prim 的关键区别在于，prim维护的是节点的集合，而 Kruskal 维护的是边的集合。如果一个图中，节点多，但边相对较少，那么使用Kruskal 更优。

数据结构与算法

Leetcode记录：最小生成树

prim算法

Kruskal算法

Table of Contents