1. 概述
在本篇文章中，我们将讨论如何计算一个图的直径（Diameter）。这个问题在图论中具有重要意义，尤其在分析网络结构时，比如交通网络、社交网络等。我们将从问题定义讲起，接着介绍解决该问题的常用算法，然后提供一段基于 Floyd-Warshall 算法的伪代码实现，并分析其时间复杂度。
2. 问题定义
图的直径定义为图中任意两点之间最短路径距离的最大值。换句话说，它等于所有点对 (u, v) 中，d(u, v) 的最大值，其中 d(u, v) 表示从顶点 u 到顶点 v 的最短路径长度。
也可以通过顶点的偏心度（eccentricity）来定义直径。一个顶点 v 的偏心度 e(v) 表示该顶点到图中其它所有顶点的最短路径中的最大值。图的直径就是所有顶点偏心度的最大值。
举个例子，如果图代表一个交通网络，那么直径就表示从一个点出发到另一个点所需的最远最短路径长度。
下图展示了一个无向图的直径（红色路径）：
我们来手动验证一下这个图的直径：
- d(A, B) = 1
- d(A, C) = 2
- d(A, D) = 2
- d(A, E) = 1
- d(B, C) = 1
- d(B, D) = 1
- d(B, E) = 2
- d(C, D) = 1
- d(C, E) = 1
- d(D, E) = 1
最大值是 2，因此该图的直径为 2。
3. 算法思路
要计算图的直径，一个通用的策略是：
✅ 计算所有点对之间的最短路径，并记录最大值
根据图的类型，可以采用不同的算法：
3.1 加权有向图（非负边权）
- Dijkstra 算法：从每个顶点出发运行一次 Dijkstra，时间复杂度为 O(n(m + n log n))，适合稀疏图
- Floyd-Warshall 算法：适用于稠密图，时间复杂度为 O(n³)，实现简单，且支持负边权（但不能有负环）
3.2 无向无权图
- BFS：对每个顶点运行一次 BFS，记录最大距离，时间复杂度为 O(n(n + m))
- 转换为加权图 + Floyd-Warshall：将所有边权设为 1，再使用 Floyd-Warshall，适合实现统一处理逻辑
4. 伪代码实现（Floyd-Warshall）
以下是一个基于 Floyd-Warshall 算法计算图直径的伪代码实现：
algorithm FloydWarshall(M):
// INPUT
// M = 一个表示图的邻接矩阵（无负环的加权有向图）
// OUTPUT
// Diameter = 图的直径
n <- M.length
d <- 创建一个 n x n x n 的三维数组
d[0] <- M
for k from 1 to n:
for i from 1 to n:
for j from 1 to n:
d[k][i][j] <- min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j])
Diameter <- d[n][0][0]
for i from 0 to n-1:
for j from 0 to n-1:
if d[n][i][j] > Diameter:
Diameter <- d[n][i][j]
return Diameter
说明：
输入是一个 n x n 的矩阵 M，其中：
- M[i][j] = 边权（若存在边）
- M[i][j] = ∞（若不存在边）
- M[i][i] = 0
使用三维数组 d[k][i][j] 来记录中间状态（k 表示当前考虑的中间节点）
最后遍历所有 d[n][i][j]，找出最大值即为直径
⚠️ 注意：实际实现中，可以优化为二维数组，避免使用三维数组浪费空间
5. 时间复杂度分析
无论采用哪种算法，计算图的直径最坏时间复杂度都是：
✅ O(n³)
其中 n 为图中节点的数量。
- Floyd-Warshall 算法包含三重循环，每层循环 n 次，内层操作为常数级，因此为 O(n³)
- 后续遍历所有点对取最大值为 O(n²)，可以忽略不计
6. 小结
本文我们介绍了图直径的定义，以及如何通过最短路径算法来计算图的直径。重点讨论了 Floyd-Warshall 算法的实现逻辑和时间复杂度。
✅ 核心要点总结如下：
| 图类型 | 推荐算法 | 时间复杂度 |
|---|---|---|
| 加权有向图（非负边权） | Dijkstra 多次调用 或 Floyd-Warshall | O(n³) |
| 无向无权图 | BFS 多次调用 或 Floyd-Warshall | O(n³) |
| 有负边权的图 | Floyd-Warshall（无负环） | O(n³) |
在实际开发中，应根据图的特性和应用场景选择合适的算法。比如社交网络、道路网络等图结构，直径可以帮助我们理解系统的“最远可达性”，是图分析中非常有价值的指标之一。