7.6.6 McCabe环路复杂度计算

McCabe 环路复杂度用来度量程序控制结构的复杂程度。它在软考中非常高频，因为题目可以直接给控制流图，也可以给伪代码、流程图，让你先转成控制流图再计算复杂度。

它度量的是什么

顺序结构只有一条路径，复杂度最低；每增加一个独立的分支或循环，就会增加一条需要关注的独立路径。McCabe 复杂度可以理解为：为了做基本路径测试，至少要设计多少条线性独立路径用例。

flowchart LR
  A["顺序结构<br/>复杂度 1"] --> B["一个 if<br/>复杂度约 2"]
  B --> C["多个判定/循环<br/>复杂度继续增加"]
  C --> D["基本路径测试<br/>用例数参考 V(G)"]

三种常用计算方法

方法	公式或规则	适合场景
边点公式	$V(G)=E-N+2$	已给控制流图，边和节点容易数
区域数法	$V(G)=$ 控制流图区域数	图形区域清楚，适合快速判断
判定节点法	$V(G)=P+1$，$P$ 为判定节点数	结构化程序中 if、while、for 等容易数

更一般的形式是 $V(G)=E-N+2C$，其中 $C$ 是连通分量数。软考常见单个连通控制流图，通常用 $V(G)=E-N+2$。

边点公式怎么数

在 $V(G)=E-N+2$ 中：

符号	含义
$E$	控制流图中的边数，即有向控制流线数量
$N$	控制流图中的节点数，即语句块或判定点数量
$V(G)$	环路复杂度，也常作为独立路径数量

数边时要数“控制能从一个节点走到另一个节点”的有向线。数节点时，不必纠结流程图上每个图形框是否都对应一个节点，关键是保持图的控制结构一致。

为什么也能用“判定节点数 + 1”

结构化程序中，每个二分判定通常会引入一个新的独立路径。因此在常见题目里：

$$V(G)=\mathrm{判}\mathrm{定}\mathrm{节}\mathrm{点}\mathrm{数}+1$$

例如有 3 个 if/while/for 判定节点，环路复杂度通常是 $3+1=4$。如果题目包含多分支 case，要按实际控制流或分支数谨慎处理，不要机械套一个节点加 1。

区域数法

控制流图画在平面上时，环路复杂度也等于区域数。区域数包括图形内部被边围出的区域，也包括最外面的外部区域。

上图只有一个二分判定，所以复杂度为 2。它对应两条独立路径：走左分支和走右分支。

从流程图或伪代码转换

考试不一定直接给控制流图。遇到流程图或伪代码时按下面步骤处理：

1. 把连续顺序语句合并为一个节点。
2. 把 if、while、for、case 等控制点画成判定节点。
3. 用有向边表示控制流走向。
4. 数边和节点，或直接数判定节点。
5. 如果图中出现交叉线，只有控制流真正汇合或分叉的地方才算节点。

课程里提醒过一个细节：有些图形为了画得清楚会多出交点或辅助点。如果你同时多算了一个节点和一条边，$E-N+2$ 的结果不变；但最好仍按真实控制流来数。

与基本路径测试的关系

基本路径测试要找一组线性独立路径。McCabe 环路复杂度给出了这组路径的数量下限。

环路复杂度	含义
1	只有顺序路径，控制结构最简单
2 到 5	复杂度较低，基本路径容易列出
6 到 10	分支较多，需要认真设计用例
大于 10	复杂度偏高，代码可维护性和测试成本上升

复杂度高不一定意味着程序错误，但意味着理解、测试和维护成本都会提高。工程上常把高复杂度函数作为重构候选。

常见失误

失误	修正
把语句行数当成复杂度	McCabe 看控制流，不看代码行数
忘记最外部区域	区域数法要包括外部区域
把所有矩形框都机械算节点	顺序语句可合并，关键是控制结构
有多个判定时漏掉循环	while、for 也是判定节点
把基本路径数理解为所有路径数	基本路径是线性独立路径，不等于穷尽所有路径

例题

单选

某程序有 2 个判定节点，按常见结构化程序计算，McCabe 环路复杂度通常为：

A1B2C3D5

单选

单个连通控制流图中，McCabe 环路复杂度常用公式是：

AV(G)=N-E+2BV(G)=E+N+2CV(G)=E-N-2DV(G)=E-N+2

本节小结

McCabe 环路复杂度衡量控制流复杂程度，也用于估算基本路径测试的独立路径数。最常用公式是 $V(G)=E-N+2$，结构化程序也常用“判定节点数 + 1”，图形题可用区域数法校验。做题时先把控制流看清楚，再选择最省事的算法。