OI-wiki 图论进阶：最小直径生成树（MDST）与图的绝对中心求解全解析-港品优选

OI-wiki 图论进阶：最小直径生成树（MDST）与图的绝对中心求解全解析

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

本文以 OI-wiki 的 mdst 文档为主体，系统讲解"最小直径生成树（Minimum Diameter Spanning Tree, MDST）"的完整求解链路：从"树的直径"这一前置概念出发，引出图的绝对中心的定义与几何直观，再到基于最短路距离数组与排序技巧的 $O(n^3 + nm)$ 求解算法，最后给出以绝对中心为根构造最短路径树从而还原 MDST 的完整 C++ 实现。读完本文，你将掌握：如何用多源最短路（Floyd / Johnson）预处理全源距离、如何利用 $\textit{rk}$ 排序数组在 $O(nm)$ 内枚举边上的绝对中心、以及如何在点中心与边中心两种情形下分别构造最小直径生成树并输出树边。

前置知识：树的直径

最小直径生成树建立在"直径"概念之上。在阅读本文前，建议先掌握树的直径的内容，其核心结论是：

树上任意两节点之间最长的简单路径即为树的"直径"；
若树上所有边权均为正，则树的所有直径中点重合。

这一"中点重合"的性质正是后面推导"图的绝对中心是最小直径生成树直径的中点"这一关键结论的基础。直径的求解有两种 $O(n)$ 方法：

两次 DFS：任意节点出发 DFS 到最远点 $z$，再从 $z$ DFS 到最远点 $z'$，$\delta(z,z')$ 即为直径（要求无负权边）；
树形 DP：记录每个点向下延伸的最长路径 $d_1$ 与次长路径 $d_2$，$d_1+d_2$ 的最大值即直径（可处理负权边）。

而本文要处理的是一般无向图上的生成树问题，直径的"中点"将推广为"图的绝对中心"。

定义：什么是最小直径生成树

在无向图的所有生成树中，直径最小的那一棵生成树就是最小直径生成树（MDST）。

直观理解：给定一张连通无向图，我们要从中选出 $n-1$ 条边构成一棵树，使得这棵树中任意两点间路径长度的最大值（即直径）最小。这并非最小生成树（MST）——MST 优化的是"边权和"，而 MDST 优化的是"树上最长路径"。

图的绝对中心

求解最小直径生成树的第一步，是找到图的绝对中心（Absolute Center）。

定义

图的绝对中心可以存在于一条边上，也可以存在于某个结点上，该中心到所有点的最短距离的最大值最小。即：

$$\min_{c \in \text{图}} \max_{i \in V} d(c, i)$$

其中 $d(c,i)$ 表示中心点 $c$ 到结点 $i$ 的最短路径长度。

根据定义可以直接推出一个重要事实：到绝对中心距离最远的结点至少有两个。否则，若最远结点唯一，沿着指向它的方向微移中心即可减小最远距离，矛盾于"最大距离最小"。

数学建模

令 $d(i,j)$ 为顶点 $i,j$ 间的最短路径长，先通过多源最短路算法求出所有结点的最短路。

定义 $\textit{rk}(i,j)$：记录点 $i$ 到其他所有结点中第 $j$ 小的那个结点。换句话说，$\textit{rk}(i)$ 是"以 $i$ 为源点的所有结点按距离升序排列"得到的序列，$\textit{rk}(i,1)$ 到 $\textit{rk}(i,n)$ 依次对应距离 $i$ 最近到最远的结点。

图的绝对中心可能在某条边上。枚举每一条边 $w=(u,v)$，并假设图的绝对中心 $c$ 就在这条边上。设中心 $c$ 距离 $u$ 的长度为 $x$（$0 \le x \le w$），则它距离 $v$ 的长度就是 $w - x$。

对于图中的任意一点 $i$，图的绝对中心 $c$ 到 $i$ 的距离为：

$$d(c,i) = \min\big(d(u,i) + x,\ d(v,i) + (w - x)\big)$$

即从 $c$ 出发到 $i$ 的最短路，要么先走到 $u$ 再走 $d(u,i)$，要么先走到 $v$ 再走 $d(v,i)$，取两者较小值。下图展示了一个结点 $i$ 与绝对中心的位置关系：结点 $i$ 既可能挂在 $u$ 一侧（经 $u$ 到达），也可能挂在 $v$ 一侧（经 $v$ 到达）。

折线函数图像

随着绝对中心 $c$ 在边 $w=(u,v)$ 上滑动（$x$ 从 0 变化到 $w$），$d(c,i)$ 也随 $x$ 变化。注意到 $d(u,i)+x$ 与 $d(v,i)+(w-x)$ 是两条斜率互为相反数（分别为 $+1$ 与 $-1$）的直线，因此 $d(c,i)$ 作为二者的 $\min$，其函数图像是一个由两条斜率相同的线段构成的折线段——先随 $x$ 增大而下降（此时 $d(v,i)+(w-x)$ 占优），在两条直线交点处转向，再随 $x$ 增大而上升（此时 $d(u,i)+x$ 占优）。

对于图上的任意一个结点都对应一条这样的折线。绝对中心到最远结点的距离函数写作：

$$f = \max{ d(c,i) },\quad i \in [1,n]$$

其函数图像是所有结点折线的上包络。这些折线交点中的最低点，其横坐标就是图的绝对中心的位置。

求解过程：完整算法

整个求解过程分为四步：

多源最短路预处理：使用 Floyd 算法（$O(n^3)$）或 Johnson 全源最短路径算法（稀疏图更优）求出 $d$ 数组；
构建排序数组：求出 $\textit{rk}(i,j)$，对每个 $i$ 按距离升序排序；
检查结点上的绝对中心：绝对中心可能恰好落在某个结点上，用距离该结点最远的结点来更新答案。遍历所有结点： $$\textit{ans} \leftarrow \min\left(\textit{ans},\ d(i,\textit{rk}(i,n)) \times 2\right)$$ 注意此时直径候选值要乘以 2（直径 = 中心到最远点的距离 × 2）；
检查边上的绝对中心：枚举所有边 $w(u,v)$，从距离 $u$ 最远的结点开始扫描。用指针 $p$ 维护"后缀最大值"：当出现 $$d\big(v,\textit{rk}(u,i)\big) > \max_{j=i+1}^{n} d\big(v,\textit{rk}(u,j)\big)$$ 的情况时，说明折线在此处发生了交点（绝对值中心位置改变），用下式更新： $$\textit{ans} \leftarrow \min\left(\textit{ans},\ d\big(u,\textit{rk}(u,i)\big) + \max_{j=i+1}^{n} d\big(v,\textit{rk}(u,j)\big) + w(u,v)\right)$$

这里第四步的精髓在于：对固定边 $(u,v)$，按 $\textit{rk}(u)$ 的升序（即 $d(u,\cdot)$ 递增）枚举结点。上包络的最低点只会出现在"$d(v,\textit{rk}(u,i))$ 大于其所有后继中最大值"的位置——这正是两条折线相交、上包络产生向下的谷底的地方。利用单调扫描 + 后缀最大值，单条边的检查可做到 $O(n)$，总复杂度 $O(nm)$。

核心代码

bool cmp(int a, int b) { return val[a] < val[b]; } void Floyd() { for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } void solve() { Floyd(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { rk[i][j] = j; val[j] = d[i][j]; } sort(rk[i] + 1, rk[i] + 1 + n, cmp); } int ans = INF; // 图的绝对中心可能在结点上 for (int i = 1; i <= n; i++) ans = min(ans, d[i][rk[i][n]] * 2); // 图的绝对中心可能在边上 for (int i = 1; i <= m; i++) { int u = a[i].u, v = a[i].v, w = a[i].w; for (int p = n, i = n - 1; i >= 1; i--) { if (d[v][rk[u][i]] > d[v][rk[u][p]]) { ans = min(ans, d[u][rk[u][i]] + d[v][rk[u][p]] + w); p = i; } } } }

注意这段实现中，结点中心与边中心两种情形得到的 $\textit{ans}$ 都是直径长度（绝对中心到最远点距离的两倍）；由于边权可能为奇数，最终输出直径时通常需要除以 2（见下文完整实现）。

例题

CodeForce 266D BerDonalds：求无向带权图的最小直径，本质就是求"图的绝对中心到最远点距离的两倍"，是本节算法的直接应用。

最小直径生成树：从绝对中心构造

原理：绝对中心即直径中点

根据图的绝对中心的定义，容易得知：图的绝对中心是最小直径生成树的直径的中点。这是因为绝对中心到所有点最远距离最小，而树中任意两点路径必然经过直径中点，于是以绝对中心为"根"生长出来的树，其最长路径（直径）恰等于 $2 \times \max_i d(c,i)$，这个值在绝对中心处取到全局最小。

因此，求解最小直径生成树需要两步：

找到图的绝对中心（方法见上文）；
以图的绝对中心为起点，生成一棵最短路径树，得到的即是最小直径生成树。

所谓最短路径树（SPT），即以某点为根、满足"根到每个结点的树上路径长度 = 该点到根的最短距离"的生成树。构造方法：对每条边 $(u,v,w)$，若 $d(P,u)+w = d(P,v)$，则边 $(u,v)$ 可被选入最短路径树。

两种情形的处理

绝对中心在结点 $P$ 上：直接以 $P$ 为根构造最短路径树即可；
绝对中心在边 $(f_1,f_2)$ 上：需要把中心"物化"为一个虚拟结点。具体做法是：新增一个结点 $n+1$ 表示中心，向 $f_1$、$f_2$ 各连一条权为 $disu$、$disv$ 的边（满足 $disu+disv=w$ 且 $disu = \dfrac{d(u,\textit{rk}(u,i)) + d(v,\textit{rk}(u,p)) + w}{2} - d(u,\textit{rk}(u,i))$），然后以虚拟结点为根构造最短路径树，最后去掉虚拟结点及其两条边即可得到原图上的最小直径生成树。

完整实现

#include <algorithm> #include <climits> #include <iostream> #include <vector> using namespace std; constexpr int MAXN = 502; using ll = long long; using pii = pair<int, int>; ll d[MAXN][MAXN], dd[MAXN][MAXN], rk[MAXN][MAXN], val[MAXN]; constexpr ll INF = 1e17; int n, m; bool cmp(int a, int b) { return val[a] < val[b]; } void floyd() { for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } struct node { ll u, v, w; } a[MAXN * (MAXN - 1) / 2]; void solve() { // 求图的绝对中心 floyd(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { rk[i][j] = j; val[j] = d[i][j]; } sort(rk[i] + 1, rk[i] + 1 + n, cmp); } ll P = 0, ansP = INF; // 绝对中心在点上 for (int i = 1; i <= n; i++) { if (d[i][rk[i][n]] * 2 < ansP) { ansP = d[i][rk[i][n]] * 2; P = i; } } // 绝对中心在边上 int f1 = 0, f2 = 0; ll disu = INT_MIN, disv = INT_MIN, ansL = INF; for (int i = 1; i <= m; i++) { ll u = a[i].u, v = a[i].v, w = a[i].w; for (int p = n, i = n - 1; i >= 1; i--) { if (d[v][rk[u][i]] > d[v][rk[u][p]]) { if (d[u][rk[u][i]] + d[v][rk[u][p]] + w < ansL) { ansL = d[u][rk[u][i]] + d[v][rk[u][p]] + w; f1 = u, f2 = v; disu = (d[u][rk[u][i]] + d[v][rk[u][p]] + w) / 2 - d[u][rk[u][i]]; disv = w - disu; } p = i; } } } cout << min(ansP, ansL) / 2 << '\n'; // 最小路径生成树 vector<pii> pp; for (int i = 1; i <= 501; ++i) for (int j = 1; j <= 501; ++j) dd[i][j] = INF; for (int i = 1; i <= 501; ++i) dd[i][i] = 0; if (ansP <= ansL) { for (int j = 1; j <= n; j++) { for (int i = 1; i <= m; ++i) { ll u = a[i].u, v = a[i].v, w = a[i].w; if (dd[P][u] + w == d[P][v] && dd[P][u] + w < dd[P][v]) { dd[P][v] = dd[P][u] + w; pp.push_back({u, v}); } u = a[i].v, v = a[i].u, w = a[i].w; if (dd[P][u] + w == d[P][v] && dd[P][u] + w < dd[P][v]) { dd[P][v] = dd[P][u] + w; pp.push_back({u, v}); } } } for (auto [x, y] : pp) cout << x << ' ' << y << '\n'; } else { d[n + 1][f1] = disu; d[f1][n + 1] = disu; d[n + 1][f2] = disv; d[f2][n + 1] = disv; a[m + 1].u = n + 1, a[m + 1].v = f1, a[m + 1].w = disu; a[m + 2].u = n + 1, a[m + 2].v = f2, a[m + 2].w = disv; n += 1; m += 2; floyd(); P = n; for (int j = 1; j <= n; j++) { for (int i = 1; i <= m; ++i) { ll u = a[i].u, v = a[i].v, w = a[i].w; if (dd[P][u] + w == d[P][v] && dd[P][u] + w < dd[P][v]) { dd[P][v] = dd[P][u] + w; pp.push_back({u, v}); } u = a[i].v, v = a[i].u, w = a[i].w; if (dd[P][u] + w == d[P][v] && dd[P][u] + w < dd[P][v]) { dd[P][v] = dd[P][u] + w; pp.push_back({u, v}); } } } cout << f1 << ' ' << f2 << '\n'; for (auto [x, y] : pp) if (x != n && y != n) cout << x << ' ' << y << '\n'; } } void init() { for (int i = 1; i <= 501; ++i) for (int j = 1; j <= 501; ++j) d[i][j] = INF; for (int i = 1; i <= 501; ++i) d[i][i] = 0; } int main() { init(); cin >> n >> m; for (int i = 1; i <= m; ++i) { ll u, v, w; cin >> u >> v >> w; w *= 2; // 边权乘 2，避免除以 2 时的精度问题 d[u][v] = w, d[v][u] = w; a[i].u = u, a[i].v = v, a[i].w = w; } solve(); return 0; }

实现要点说明：

边权乘 2：main中读入边权后立即w *= 2，此后所有距离均为偶数，disu、直径等计算结果可直接整除，避免浮点误差；最终输出直径时再min(ansP, ansL) / 2还原；
排序键：cmp依赖全局数组val，val[j] = d[i][j]需在每次排序前写入，故rk[i]的排序逐行进行；
后缀最大值指针：边中心扫描中p始终指向"当前已扫描结点的后缀中 $d(v,\cdot)$ 最大的结点"，当d[v][rk[u][i]] > d[v][rk[u][p]]时即出现交点，更新答案并把p移动到i；
最短路径树判定：dd[P][u] + w == d[P][v]判定边 $(u,v)$ 落在从 $P$ 出发的最短路径上（即三角形等式成立），dd[P][u] + w < dd[P][v]则保证每个点只被其最短路径上的"前驱"第一次更新时选中，配合dd数组去重，避免输出重复边；
虚拟结点：边中心情形下以虚拟结点 $n+1$ 为根建树后，输出树边时需过滤掉包含虚拟结点的边（x != n && y != n），并在输出前先输出真实边 $(f_1,f_2)$ 补全树的连通性。

复杂度分析

步骤	复杂度
多源最短路（Floyd）	$O(n^3)$
构造 $\textit{rk}$ 排序数组（$n$ 次排序）	$O(n^2 \log n)$
枚举结点上的绝对中心	$O(n)$
枚举边上的绝对中心（$m$ 条边 × $O(n)$ 扫描）	$O(nm)$
最短路径树构造	$O(nm)$
总复杂度	$O(n^3 + nm)$（Johnson 预处理时稀疏图为 $O(nm\log n)$）

在 $n$ 较小（如 $n \le 500$）的稠密图上，Floyd + $O(nm)$ 扫描的整套流程可在 $O(n^3)$ 内完成，这也是上述代码将MAXN设为 502 的适用场景。

例题

SPOJ MDST：最小直径生成树的模板题，直接应用上述算法；
timus 1569. Networking the "Iset"：求给定网络的最小直径生成树（实际为最小半径生成树问题，与 MDST 思路相通）；
SPOJ PT07C - The GbAaY Kingdom：树上的最小直径生成树，本质是求树的绝对中心（即树的半径），可用两次 DFS / 树形 DP 简化求解。

总结

最小直径生成树问题的求解可以浓缩为一条清晰的链路：

预处理全源最短路（Floyd / Johnson）；
按距离排序构建 $\textit{rk}$ 数组；
求图的绝对中心：结点中心直接取 $\max_i d(i,j)$ 最小者，边中心用"折线上包络最低点"的几何视角配合后缀最大值指针在 $O(nm)$ 内枚举；
以绝对中心为根构造最短路径树：结点中心直接建树，边中心通过虚拟结点物化中心后建树再还原。

整个算法将"生成树直径最小化"这一全局优化问题，转化为"在边的连续区间上寻找函数包络最低点"的几何问题，再落到排序 + 单调扫描的工程实现上，是图论中"连续最优化离散化求解"的经典范例。三张配套示意图（位置关系图、单折线函数图、包络最低点图）分别从结构与函数两个角度直观呈现了这一过程，其原始 TikZ 源码可参考 mdst-graph.tex、mdst-plot1.tex 与 mdst-plot2.tex，便于读者复现与改造图示。

参考文献

Play with Trees Solutions The GbAaY Kingdom

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

企业官网建设流程全解析