【STMT】McCabe环路复杂度

McCabe环路复杂度

McCabe环路复杂度用于度量程序逻辑复杂性，计算程序的基本独立路径数目，即确保所有语句至少执行一次的最小测试数量。
McCabe环路复杂度需要先根据代码画出程序流程图，然后画出对应的程序控制流图，再通过以下三种方法计算：

• 给定流图$G$G的边数$m$m，结点数$n$n，那么环路复杂度$V(G) = m - n + 2$V(G)=m−n+2
• 根据欧拉拓扑公式$V + F - E = X(P)$V+F−E=X(P)，$V$V是多面体$P$P的顶点数，$F$F是多面体$P$P的面数，$E$E是多面体$P$P的棱数，应用于平面时$X(P) = 2$X(P)=2，得$E - V + 2 = F$E−V+2=F，因此环路复杂度即流图$G$G的区域数
• 给定流图$G$G的单判定结点数$d$d，那么环路复杂度$V(G) = d + 1$V(G)=d+1

独立路径

一条独立路径是指，和其它的独立路径相比，至少引入一个新处理语句或一个新判断的程序通路，一个程序的独立路径条数等于环路复杂度。
需要注意的是，独立路径条数并非覆盖所有路径的最小路径数，一条程序通路只需要满足与其它任意独立路径相比都至少覆盖一条新的路径就是一条独立路径，哪怕这条通路上的所有路径都已经被其它独立路径覆盖了也没关系。举个例子，类似于$8$8字的程序流图有$3$3条而不是$2$2条独立路径。

题目

程序流程图如下，计算环路复杂度并找出一个独立路径集合。

解答

首先给程序流程图加入编号如下

然后画出程序控制流图如下

计算McCabe环路复杂度如下

• $m = 10$m=10，$n = 7$n=7，$V(G) = m - n + 2 = 5$V(G)=m−n+2=5
• $V(G) = F = 5$V(G)=F=5
• $d = 4$d=4，$V(G) = d + 1 = 5$V(G)=d+1=5

一个独立路径集合如下

• 路径1：1 - 2 - 5,6 - 9
• 路径2：1 - 2 - 3,4 - 5,6 - 9
• 路径3：1 - 3,4 - 5,6 - 9
• 路径4：1 - 3,4 - 5,6 - 7 - 9
• 路径5：1 - 3,4 - 5,6 - 7 - 8 - 9