Next Quiz

次小生成树(SMST)

数据结构与算法第五章图(gragh) 次小生成树(SMST)

组别：提高组
难度：7

次小生成树（Second Minimum Spanning Tree，SMST）是指在图中除了最小生成树（MST）之外的生成树中权值最小的一个。求次小生成树的常见方法包括以下几种：

方法一：暴力法

先求出最小生成树。
从最小生成树中去掉一条边，再加上一条不在生成树中的边，形成新的生成树，计算其权值。
通过枚举所有可能的组合，找出次小的生成树。

方法二：DFS遍历边

先求出最小生成树。
枚举每一条不在MST中的边，尝试将其加入MST，并从MST中找出一条边替换，使得新的生成树权值最小。
通过DFS遍历，计算出每个非树边对应的次小生成树的权值。

方法三：LCA优化

先求出最小生成树。
对于每条非树边(u,v)(u, v)(u,v)，在MST中找出从u到v路径上的最大边。
用非树边替换路径上最大边，计算得到的生成树的权值。
使用LCA（Lowest Common Ancestor）算法进行路径查询和更新，可以提高计算效率。

代码实现：

这段代码实际上是使用了方法一的一部分（暴力法）和方法二的一部分（DFS遍历边）的结合，但并没有完全实现方法三（LCA优化）。

方法一的部分实现：代码中通过Kruskal算法先求得了最小生成树（MST）。
方法二的部分实现：在findSecondMST函数中，代码尝试通过枚举非MST中的边，来替换MST中的一条边，以此计算出新的生成树的权值。不过代码并没有使用DFS遍历来找到最大边，而是简单地遍历所有MST中的边来进行替换。

/**************************************************************** 
 * Description: 次小生成树
 * Author: Alex Li
 * Date: 2024-08-13 11:10:39
 * LastEditTime: 2024-08-13 11:11:07
****************************************************************/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
struct Edge {
    int u, v, weight;  // 边的两个端点及其权重
    bool inMST;        // 标记此边是否在最小生成树中
};

vector<Edge> edges;      // 存储所有的边
vector<int> parent, rank; // 并查集的父节点数组和秩数组

// 查找并查集的根节点
int find(int u) {
    // 路径压缩优化，直接将u的父节点指向根节点
    return u == parent[u] ? u : parent[u] = find(parent[u]);
}

// 合并两个集合
bool unionSets(int u, int v) {
    u = find(u);  // 找到u的根节点
    v = find(v);  // 找到v的根节点
    if (u != v) { // 如果两个节点不在同一个集合中
        // 按秩合并，将秩低的集合合并到秩高的集合中
        if (rank[u] > rank[v]) swap(u, v);
        parent[u] = v;   // 将u的根节点合并到v的根节点
        if (rank[u] == rank[v]) rank[v]++; // 如果秩相同，增加v的秩
        return true;
    }
    return false; // 如果已经在同一个集合中，则不合并
}

// Kruskal算法求最小生成树
int kruskal(int n) {
    // 按边权排序
    sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
        return a.weight < b.weight;
    });

    // 初始化并查集
    parent.resize(n);
    rank.resize(n);
    for (int i = 0; i < n; ++i) {
        parent[i] = i; // 每个节点的父节点初始化为自己
        rank[i] = 0;   // 初始时每个节点的秩为0
    }

    int mst_weight = 0; // MST的总权重
    int mst_edges = 0;  // MST中的边数量
    for (Edge &e : edges) {
        // 尝试将当前边加入MST
        if (unionSets(e.u, e.v)) {
            mst_weight += e.weight; // 累加边的权重
            e.inMST = true;         // 标记该边在MST中
            mst_edges++;            // 计数MST中的边数
            if (mst_edges == n - 1) break; // 当MST中的边数达到n-1时停止
        }
    }
    return mst_weight; // 返回最小生成树的总权重
}

// 计算次小生成树的权重
int findSecondMST(int n, int mst_weight) {
    int second_mst = INT_MAX; // 初始化次小生成树的权重为无穷大

    // 枚举每条不在MST中的边
    for (Edge &e : edges) {
        if (!e.inMST) {
            // 尝试加入非树边e，删除MST中的最大边
            for (Edge &tree_edge : edges) {
                if (tree_edge.inMST && tree_edge.weight < e.weight) {
                    // 计算新的生成树权值
                    int new_weight = mst_weight + e.weight - tree_edge.weight;
                    // 更新次小生成树的权重
                    second_mst = min(second_mst, new_weight);
                }
            }
        }
    }
    return second_mst; // 返回次小生成树的权重
}

int main() {
    int n, m;  // n为节点数，m为边数
    cin >> n >> m;
    edges.resize(m);  // 调整边数组的大小以容纳所有边
    for (int i = 0; i < m; ++i) {
        // 输入每条边的两个端点及其权重
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
        edges[i].inMST = false;  // 初始化时每条边都不在MST中
    }

    int mst_weight = kruskal(n); // 求出最小生成树的权重
    int second_mst_weight = findSecondMST(n, mst_weight); // 求出次小生成树的权重

    // 输出结果
    cout << "最小生成树权值: " << mst_weight << endl;
    cout << "次小生成树权值: " << second_mst_weight << endl;

    return 0;
}

代码二：LCA优化

在MST中找到两点之间的路径上的最大边。这种方法通常使用倍增法或RMQ（Range Minimum Query）进行LCA查询。

/**************************************************************** 
 * Description: 次小生成树 LCA实现
 * Author: Alex Li
 * Date: 2024-08-13 11:14:40
 * LastEditTime: 2024-08-13 11:17:56
****************************************************************/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Edge {
    int u, v, weight;
    bool inMST;
};

vector<Edge> edges;
vector<int> parent, rank;
vector<vector<int>> adj; // 图的邻接表
vector<vector<int>> parentLCA; // LCA的父节点倍增表
vector<vector<int>> maxEdgeLCA; // LCA的最大边权倍增表
vector<int> depth; // 节点深度

// 查找并查集的根节点
int find(int u) {
    return u == parent[u] ? u : parent[u] = find(parent[u]);
}

// 合并两个集合
bool unionSets(int u, int v) {
    u = find(u);
    v = find(v);
    if (u != v) {
        if (rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if (rank[u] == rank[v]) rank[v]++;
        return true;
    }
    return false;
}

// Kruskal算法求最小生成树
int kruskal(int n) {
    sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
        return a.weight < b.weight;
    });

    parent.resize(n);
    rank.resize(n);
    adj.resize(n);
    for (int i = 0; i < n; ++i) {
        parent[i] = i;
        rank[i] = 0;
    }

    int mst_weight = 0;
    int mst_edges = 0;
    for (Edge &e : edges) {
        if (unionSets(e.u, e.v)) {
            mst_weight += e.weight;
            e.inMST = true;
            adj[e.u].push_back(e.v);
            adj[e.v].push_back(e.u);
            mst_edges++;
            if (mst_edges == n - 1) break;
        }
    }
    return mst_weight;
}

// DFS初始化节点深度和父节点表
void dfs(int u, int p, int d, vector<vector<int>>& maxEdge) {
    depth[u] = d;
    parentLCA[u][0] = p;
    for (int v : adj[u]) {
        if (v != p) {
            maxEdgeLCA[v][0] = maxEdge[u][v];
            dfs(v, u, d + 1, maxEdge);
        }
    }
}

// 预处理LCA的父节点和最大边权倍增表
void preprocessLCA(int n) {
    int logN = log2(n) + 1;
    parentLCA.assign(n, vector<int>(logN, -1));
    maxEdgeLCA.assign(n, vector<int>(logN, 0));
    depth.assign(n, 0);

    // 初始DFS，设置深度和1层父节点
    for (int u = 0; u < n; ++u) {
        if (depth[u] == 0) {
            dfs(u, -1, 0, maxEdgeLCA);
        }
    }

    // 倍增法预处理LCA和最大边权
    for (int j = 1; j < logN; ++j) {
        for (int i = 0; i < n; ++i) {
            if (parentLCA[i][j - 1] != -1) {
                parentLCA[i][j] = parentLCA[parentLCA[i][j - 1]][j - 1];
                maxEdgeLCA[i][j] = max(maxEdgeLCA[i][j - 1], maxEdgeLCA[parentLCA[i][j - 1]][j - 1]);
            }
        }
    }
}

// LCA查询，返回u和v路径上的最大边权
int queryLCA(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);

    int logN = log2(depth[u]);
    int maxEdge = 0;

    // 使u和v在同一深度
    for (int i = logN; i >= 0; --i) {
        if (depth[u] - (1 << i) >= depth[v]) {
            maxEdge = max(maxEdge, maxEdgeLCA[u][i]);
            u = parentLCA[u][i];
        }
    }

    if (u == v) return maxEdge;

    // 同时向上跳
    for (int i = logN; i >= 0; --i) {
        if (parentLCA[u][i] != parentLCA[v][i]) {
            maxEdge = max({maxEdge, maxEdgeLCA[u][i], maxEdgeLCA[v][i]});
            u = parentLCA[u][i];
            v = parentLCA[v][i];
        }
    }

    // 最后一步到达LCA
    maxEdge = max({maxEdge, maxEdgeLCA[u][0], maxEdgeLCA[v][0]});
    return maxEdge;
}

// 计算次小生成树的权重
int findSecondMST(int n, int mst_weight) {
    int second_mst = INT_MAX;

    // 枚举每条不在MST中的边
    for (Edge &e : edges) {
        if (!e.inMST) {
            // 查询u和v的LCA路径上的最大边
            int maxEdge = queryLCA(e.u, e.v);
            // 计算替换后的生成树权值
            int new_weight = mst_weight + e.weight - maxEdge;
            // 更新次小生成树的权重
            second_mst = min(second_mst, new_weight);
        }
    }
    return second_mst;
}

int main() {
    int n, m;
    cin >> n >> m;
    edges.resize(m);
    vector<vector<int>> maxEdge(n, vector<int>(n, 0)); // 最大边矩阵
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
        edges[i].inMST = false;
        maxEdge[edges[i].u][edges[i].v] = edges[i].weight;
        maxEdge[edges[i].v][edges[i].u] = edges[i].weight;
    }

    int mst_weight = kruskal(n);
    preprocessLCA(n);
    int second_mst_weight = findSecondMST(n, mst_weight);

    cout << "最小生成树权值: " << mst_weight << endl;
    cout << "次小生成树权值: " << second_mst_weight << endl;

    return 0;
}

Previous Topic

Back to Lesson

Next Quiz