h5页面制作工具哪个好_怎么做营销推广_市场营销公司_香港疫情最新情况

图论 —— 生成树 —— 次小生成树_次小生成树怎么求-CSDN博客

语雀版本

1 概念

如果一个图G的最小生成树是T，则除T外的第二小生成树，即为次小生成树。

次小生成树可能权值和与最小生成树相同，但肯定不可能小于最小生成树。

2 Prim求解

使用 Prim 算法求解无向连通图的次小生成树。主要步骤包括：

1. 构建最小生成树（MST）：
   • 使用 Prim 算法，从任意节点开始构建 MST。
   • 在构建过程中，记录每条被选中的边，并将其加入 MST 的邻接表 MST[N] 中。
   • 同时，使用二维数组 inMST[N][N] 标记哪些边已经在 MST 中。
2. 计算 MST 中任意两点之间路径上的最大边权值：
   • 对于 MST 中的每个节点，执行广度优先搜索（BFS），计算从该节点到其他节点路径上的最大边权值。
   • 结果存储在二维数组 maxDis[N][N] 中，maxDis[i][j] 表示在 MST 中从节点 i 到节点 j 的路径上最大边权值。
3. 寻找次小生成树：
   • 遍历所有不在 MST 中的边（即 inMST[u][v] == false 的边）。
   • 对于每条这样的边 (u, v)，尝试替换 MST 中从 u 到 v 路径上的最大边，以形成新的生成树。
   • 计算新的生成树的总权值 temp = res - maxDis[u][v] + G[u][v]。
     • 如果 temp == res，说明存在另一棵与 MST 权值相同的生成树，最小生成树不唯一。
     • 如果 temp > res 且小于当前记录的次小生成树的总权值，则更新次小生成树的总权值。
4. 输出结果：
   • 如果最小生成树不唯一，输出 "Not Unique!"。
   • 如果存在次小生成树，输出其总权值。
   • 如果不存在次小生成树，输出 "No second way"。

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>#define INF 0x3f3f3f3f
const int N = 510;int n, m;
int G[N][N]; // 邻接矩阵，存储图的边权
bool vis[N]; // 标记节点是否已访问
int dis[N], per[N]; // Prim 算法中的距离和父节点
int res; // 最小生成树的总权值
std::vector<std::pair<int, int>> MST[N]; // 最小生成树的邻接表
bool inMST[N][N]; // 标记边是否在最小生成树中
int maxDis[N][N]; // 存储最小生成树中两点之间路径上的最大边权值
std::vector<std::tuple<int, int, int>> edgeList; // 存储所有边的信息void prim() {memset(vis, false, sizeof(vis));memset(inMST, false, sizeof(inMST));// 初始化距离和父节点for (int i = 1; i <= n; i++) {dis[i] = INF;per[i] = -1;}dis[1] = 0; // 从节点 1 开始res = 0;    // 最小生成树的总权值for (int i = 1; i <= n; i++) {int u = -1, minDis = INF;// 找到未访问的、距离已访问集合最近的节点for (int j = 1; j <= n; j++) {if (!vis[j] && dis[j] < minDis) {u = j;minDis = dis[j];}}if (u == -1)return; // 图不连通vis[u] = true;    // 标记节点已访问res += dis[u];    // 累加边权if (per[u] != -1) {int v = per[u];// 将边加入最小生成树MST[u].push_back({v, dis[u]});MST[v].push_back({u, dis[u]});inMST[u][v] = inMST[v][u] = true; // 标记边已在最小生成树中}// 更新其他节点到已访问集合的最小距离for (int v = 1; v <= n; v++) {if (!vis[v] && G[u][v] < dis[v]) {dis[v] = G[u][v];per[v] = u;}}}
}// 计算最小生成树中任意两点之间路径上的最大边权值
void computeMaxDis() {for (int i = 1; i <= n; i++) {// 初始化memset(vis, false, sizeof(vis));std::queue<int> q;vis[i] = true;maxDis[i][i] = 0;q.push(i);// 广度优先搜索while (!q.empty()) {int u = q.front();q.pop();for (auto &edge : MST[u]) {int v = edge.first;int w = edge.second;if (!vis[v]) {vis[v] = true;// 更新最大边权值maxDis[i][v] = std::max(maxDis[i][u], w);q.push(v);}}}}
}int main() {scanf("%d%d", &n, &m);memset(G, INF, sizeof(G));// 读取图的边信息并初始化for (int i = 0; i < m; i++) {int u, v, w;scanf("%d%d%d", &u, &v, &w);G[u][v] = G[v][u] = w;edgeList.push_back(std::make_tuple(u, v, w));}prim();          // 构建最小生成树并计算总权值computeMaxDis(); // 计算最小生成树中任意两点之间的最大边权值int second_min_res = INF;bool flag = false; // 用于判断最小生成树是否唯一// 遍历所有边，尝试替换生成次小生成树for (auto &e : edgeList) {int u = std::get<0>(e);int v = std::get<1>(e);int w = std::get<2>(e);// 如果边不在最小生成树中if (!inMST[u][v]) {// 计算替换后的总权值int temp = res - maxDis[u][v] + w;if (temp == res) {flag = true; // 存在权值相同的最小生成树，说明最小生成树不唯一} else if (temp > res && temp < second_min_res) {second_min_res = temp; // 更新次小生成树的总权值}}}if (flag) {printf("Not Unique!\n"); // 最小生成树不唯一} else if (second_min_res != INF) {printf("%d\n", second_min_res); // 输出次小生成树的总权值} else {printf("No second way\n"); // 不存在次小生成树}return 0;
}

3 Kruskal求解

**算法步骤：**

1. Kruskal 算法构建最小生成树（MST）：
   • 排序边集： 将所有边按照权值从小到大排序。
   • 初始化并查集： 每个节点自成一个集合，用于检测环路。
   • 逐边加入 MST：
     • 对于每条边，判断其两个端点是否属于不同的集合（即是否连通）。
     • 如果不连通，则将该边加入 MST，并合并两个集合。
     • 在加入边的过程中，更新 maxDis 数组，记录 MST 中任意两点之间路径上的最大边权值。
2. 更新 **maxDis** 数组：
   • 在合并两个连通分量时，遍历两个分量中的所有节点对，更新它们之间的最大边权值为当前合并的边的权值。
   • 由于 Kruskal 算法按边权从小到大加入边，因此后续加入的边权值只会更大。
3. 寻找次小生成树（SMST）：
   • 遍历所有未被使用的边（不在 MST 中的边）。
   • 对于每条这样的边 (u, v, w)：
     • 如果在 MST 中，节点 u 和 v 之间存在路径，则可以尝试替换 MST 中的某条边以形成新的生成树。
     • 计算替换后的总权值：temp = mst + w - maxDis[u][v]。
     • 更新次小生成树的权值 smst。
   • 判断 MST 的唯一性：
     • 如果 smst == mst，说明存在另一棵权值相同的生成树，最小生成树不唯一。
     • 如果 smst > mst，说明最小生成树是唯一的。
4. 输出结果：
   • 如果最小生成树不唯一，输出 "Not Unique!"。
   • 如果唯一，输出最小生成树的总权值。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>#define INF 0x3f3f3f3f
const int N = 1010;int n, m;struct Edge {int u, v, w;bool vis; // 标记边是否在最小生成树中bool operator<(const Edge &rhs) const {return w < rhs.w; // 按边权从小到大排序}
} edges[N * N];std::vector<int> G[N]; // 存储每个连通分量中的节点
int father[N];         // 并查集数组
int maxDis[N][N];      // 存储最小生成树中任意两点之间路径上的最大边权值// 并查集查找函数，带路径压缩
int Find(int x) {return x == father[x] ? x : father[x] = Find(father[x]);
}void Kruskal() {// 按边权从小到大排序std::sort(edges, edges + m);// 初始化并查集和连通分量for (int i = 1; i <= n; i++) {G[i].clear();G[i].push_back(i); // 初始时每个节点自成一个集合father[i] = i;}int mst = 0;      // 最小生成树的总权值int numEdges = 0; // 最小生成树中的边数// 初始化 maxDis 数组for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)maxDis[i][j] = -INF; // -INF 表示两点之间的最大边权值未被更新// Kruskal 算法构建最小生成树for (int i = 0; i < m; i++) {if (numEdges == n - 1)break; // 最小生成树已构建完成int u = edges[i].u;int v = edges[i].v;int w = edges[i].w;int fu = Find(u);int fv = Find(v);if (fu != fv) {// 将边加入最小生成树numEdges++;mst += w;edges[i].vis = true; // 标记边已在最小生成树中// 更新不同连通分量之间的 maxDisint lenU = G[fu].size();int lenV = G[fv].size();for (int j = 0; j < lenU; j++) {int nodeU = G[fu][j];for (int k = 0; k < lenV; k++) {int nodeV = G[fv][k];// 更新节点对之间的最大边权值为当前边的权值maxDis[nodeU][nodeV] = w;maxDis[nodeV][nodeU] = w; // 对称更新}}// 合并两个连通分量father[fu] = fv;// 合并节点列表G[fv].insert(G[fv].end(), G[fu].begin(), G[fu].end());G[fu].clear(); // 清空被合并的集合（可选）}}int smst = INF; // 次小生成树的权值// 尝试找到次小生成树for (int i = 0; i < m; i++) {if (!edges[i].vis) {int u = edges[i].u;int v = edges[i].v;int w = edges[i].w;// 计算可能的次小生成树权值int temp = mst + w - maxDis[u][v];if (temp == mst) {// 存在权值相同的最小生成树smst = mst;break;} else if (temp < smst) {smst = temp;}}}if (smst == mst) {printf("Not Unique!\n"); // 最小生成树不唯一} else {printf("%d\n", mst); // 输出最小生成树的总权值}
}int main() {scanf("%d%d", &n, &m);// 读取边的信息for (int i = 0; i < m; i++) {scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);edges[i].vis = false;}Kruskal();return 0;
}