1. 引言
在本文中，我们将深入讲解 圈复杂度（Cyclomatic Complexity） 的概念与计算方法。圈复杂度是衡量软件模块稳定性与可维护性的重要指标之一，最早由 Thomas J. McCabe 于 1976 年提出。
根据 IBM Rational Asset Analyzer 的定义，圈复杂度越高，模块越复杂，潜在缺陷也越多。因此，建议将高复杂度的模块拆分成更小的子模块，以提升代码可读性和可测试性。
对于有经验的开发人员来说，圈复杂度是一个非常实用的工具，尤其在代码审查、重构和质量评估中具有重要意义。
2. 问题描述
设 M 为一个软件模块，其圈复杂度表示为 M 中线性无关路径的数量。路径指的是从模块入口到出口的控制流路径。
举个简单的例子，看下面这段伪代码：
algorithm CheckTheInteger(x):
// INPUT
// x = an integer
// OUTPUT
// No output
if x < 100:
print x "is less than 100"
else:
print x "is greater than or equal to 100"
这个模块中存在两个线性无关路径：
- x < 100
- x >= 100
所以，其圈复杂度为 2。
3. 圈复杂度定义与计算方式
圈复杂度的核心在于控制流图（Control Flow Graph, CFG）。CFG 是对模块结构的抽象表示，其中：
- 每个节点表示一个没有跳转的代码块（即顺序执行的语句）
- 每条有向边表示控制流的跳转
一个线性无关路径指的是从 CFG 的入口节点到出口节点的一条路径。
如下图所示，是一个 switch 语句的 CFG 示例：
该 CFG 中有 3 个线性无关路径。
3.1 方法一：基于 CFG 的节点与边数计算
设 CFG 中：
- 节点数为 n
- 边数为 e
- 连通分量数为 c（通常为 1）
则圈复杂度 V(G) 的计算公式为：
V(G) = e - n + 2c
3.2 方法二：基于决策节点数计算
根据 McCabe 的原始论文，圈复杂度也可以通过以下公式计算：
V(G) = 决策节点数 + 1
其中决策节点指的是控制流中存在分支的语句，包括：
- if、while、for 等含有条件判断的语句
- switch 中的每个 case（不包括 default）
比如以下代码：
if (x > 5) {
// ...
} else {
// ...
}
这里 if 语句是一个决策节点，因此圈复杂度为 1 + 1 = 2。
4. 示例详解
我们来看一个更复杂的例子：
algorithm CheckTheInteger(x):
// INPUT
// x = an integer
// OUTPUT
// No output
while x < 10:
if x > 5:
print x
else:
print x "is less than 6"
x <- x + 1
该模块的 CFG 如下图所示：
4.1 方法一计算
- 节点数 n = 6
- 边数 e = 7
- 连通分量数 c = 1
代入公式：
V(G) = 7 - 6 + 2 * 1 = 3
说明该模块有 3 条线性无关路径：
4.2 方法二计算
模块中有两个决策节点：
- while x < 10
- if x > 5
因此决策节点数为 2，圈复杂度为：
V(G) = 2 + 1 = 3
两种方法得出的结果一致。
5. 时间复杂度分析
为了计算圈复杂度，我们需要遍历 CFG，统计节点、边和决策节点数量。这通常通过 DFS（深度优先搜索）实现。
设 CFG 中节点数为 N，边数为 E，则 DFS 的时间复杂度为：
O(N + E)
若 CFG 使用邻接表表示，这个复杂度是高效的，适用于大多数实际项目中的函数或模块分析。
6. 总结
✅ 圈复杂度是衡量代码复杂度的重要指标，有助于识别潜在的高风险模块。
✅ 有两种主流计算方式：一种基于 CFG 的结构（节点、边、连通分量），另一种基于决策节点的数量。
✅ 实际开发中，推荐使用静态分析工具（如 SonarQube、Checkstyle）自动计算圈复杂度。
❌ 高圈复杂度往往意味着模块难以测试和维护，应优先重构。
⚠️ 一般来说，建议单个函数的圈复杂度不超过 10。
圈复杂度虽不是万能指标，但在代码质量评估中具有重要参考价值。熟练掌握其计算方法，有助于我们在开发过程中更早发现问题，提升代码可维护性。