扫码获取 VIP 码
添加管理员微信获取 VIP 码
McCabe度量法由美国计算机科学家Thomas McCabe于1976年在其经典论文中正式提出，其核心思想是用图论的方法来量化程序的复杂性。在软件工程领域，程序的复杂性直接影响测试成本、维护难度和缺陷密度，而McCabe度量法用一种简洁的数学公式将程序的控制结构映射为可度量的数值，这就是环形复杂度。环形复杂度的英文为Cyclomatic Complexity，它的原始定义是：对于一个强连通的有向图，环形复杂度等于图中的线性无关环路的数量。在程序控制流图中，McCabe将其推广为一般有向图的圈复杂度计算。控制流图中的每个基本块对应一个节点，每个条件跳转或顺序转移对应一条有向边，当程序的控制流从入口节点到出口节点形成闭合时，环形复杂度就是图中独立路径的条数。这里的独立路径指的是一条路径至少包含一条其他路径没有覆盖到的边，所有独立路径的集合构成了程序路径覆盖的最小基。软考中常考的是简化后的三个等价公式，它们分别从图的边与节点关系、判定节点数量、封闭区域数量三个角度给出了环复杂度的计算方法，但三个公式的适用前提和容易记混的地方恰恰是命题人反复设陷阱的重点区域。
McCabe环形复杂度有三个等价的计算公式，它们来源于图论中的欧拉公式推广。第一个公式基于边与节点的关系：环形复杂度等于控制流图中边的数量减去节点的数量再加二，即V(G)=e-n+2。这个公式适用于单入口单出口的控制流图，其图论本质是将程序的控制流图加上一条从出口指向入口的虚拟边使其成为强连通图后，独立环路数目等于边数减节点数加一，再加一修正项得到最终结果。第二个公式基于判定节点的数量：环形复杂度等于判定节点数加一，即V(G)=P+1。其中判定节点是指控制流图中具有两个或以上出边的节点，通常对应程序中的条件判断语句。这个公式的直观理解是每个判断点贡献了一个分支路径，而基线路径本身对应值一，所以总数是判定节点数加一。第三个公式基于平面图的封闭区域数：环形复杂度等于控制流图中封闭区域的数量加一，即V(G)=R+1。这里的区域是图论中平面图划分出的连通区域，包括最外层无限区域在内的所有区域总数恰好等于V(G)。需要注意的是R仅计算封闭区域即内部面区域，加上最外层的无限区域后正好等于V(G)。三个公式在标准条件下完全等价，但实际考试中根据题目给出的信息类型不同，需要灵活选用合适的公式。当题目给出了控制流图的边和节点数量时用第一个公式最直接，当题目只给出了判断语句的分布时用第二个公式最高效，当题目给出了控制流图并要求识别区域时用第三个公式最直观。三个公式的等价性可以通过一个具体例子来验证，假设某程序的控制流图有八个节点和十条边，按第一条公式V(G)=10-8+2=4，控制流图中有一个if-else结构和两个while循环共三个判定节点，按第二条公式V(G)=3+1=4，控制流图绘制在平面上后可以识别出三个封闭区域，按第三条公式V(G)=3+1=4，三种算法殊途同归验证了公式的等价性。
在实际的软件开发和质量保障活动中McCabe度量法有明确的应用场景和量化标准。首先是模块级别的复杂度度量，McCabe建议单个模块的环形复杂度不应超过十，超过十的模块通常被认为结构过于复杂，需要进行重构拆分。这一阈值被广泛采纳为软件质量度量的事实标准，也被纳入许多企业的编码规范中。其次是测试用例数的估算，环形复杂度直接给出了基本路径覆盖所需的最少测试用例数量，测试人员只需为每条独立路径设计一个测试用例即可实现语句覆盖和判定覆盖的中间级别覆盖标准，这一特性使得McCabe度量法成为白盒测试路径覆盖规划的理论基础。再次是缺陷密度的预测，大量的实证研究表明环形复杂度越高的模块其缺陷密度也趋于越高，复杂度超过三十的模块往往集中了项目大部分的生产缺陷。McCabe度量法的边界条件也需要注意，它适用于结构化程序设计语言编写的模块，对于面向对象程序中由多态引起的动态绑定其控制流图构建需要特别处理。另外对于程序中包含异常处理机制的复杂控制流McCabe度量法倾向于高估复杂度，因为异常处理路径在实际运行中很少被触发但每个异常处理块都会增加环形复杂度。软考中特别需要关注的一个细节是循环结构对环形复杂度的影响，一个普通的while或for循环在控制流图中引入一条回边从而产生一个封闭区域，等价于一个判定节点，因此每个循环贡献的环形复杂度增量为壹。嵌套循环中的每一层都独立贡献一个增量而非按嵌套层级累乘。此外连续的条件判断与组合条件判断在控制流图中的表示也有所不同，连续的if-elseif-else结构在控制流图中产生多个判定节点，而单个if语句中的逻辑与或逻辑或组合条件在控制流图中通常只计为一个判定节点，因为它们是同一个条件表达式求值的结果，这一区别在考试中极易被忽视。