关于软件白盒测试中的路径测试：构建程序图规则、正确计算环复杂度的公式方法、通用计算方法、不同计算方法之间关联

• 程序图与环复杂度
• • 1.程序图的构建规则
  • 2.环复杂度计算方法
  • 3.不适用普通方法的情况（多输入多输出/多分支判定节点）如何处理
  • 小结

程序图与环复杂度

程序图，是一种用以表示程序结构的有向图。程序图可以根据代码的逻辑结构构建，并且相对流程图有一定的简化规则。建立程序图可以为计算环复杂度、度量程序复杂程度提供基础。
环复杂度，是McCabe复杂性度量方法，即软件白盒测试方法中路径测试的一种指标，用以度量程序图的复杂程度。环复杂度也可以形象化地理解为程序图这一有向图中环的数目。
建立程序图从而测算出的环复杂度，可以作为路径测试中，度量独立路径数目的依据。

2. 通用的环复杂度计算方法:
部分环复杂度计算公式对图的形式存在要求，即要求其为强连通图或者为单输入单输出图。
“如何对任意程序图进行环复杂度的通用度量呢strong>”

3. 关于不同环复杂度度量方法的互相印证：
目前已知的环复杂度的主要度量方法共有：观察法、公式法、分支节点法三种。三者方法的度量结果是否能够达成一致，如何一致p>

1.程序图的构建规则

2)公式计算法
环复杂度计算公式有两个版本：
(1)VF=E-N+2; 适用条件：单输入、单输出。
(2)VF=E-N+1; 适用条件：强连通图。
E为边数，N为节点数。
这两个公式都是正确的，但是使用条件不同。
还是考虑上图：

3)判定节点法
判定节点法指的是根据程序图中二分支判定节点的数目确定环复杂度。
当图中存在非二分支判定节点，则图的环复杂度不可以用这种方法确定。
判定节点在实践意义上指的是程序中的if-else类的分支语句，在程序图中可以根据单输入多分支的图形确认分支节点的位置和数量。
公式为VF=判定节点数+1

3.不适用普通方法的情况（多输入多输出/多分支判定节点）如何处理

那么，公式法如何应对呢r> 根据上述辅助线的填法，当图改为强连通图时，即可利用VF=E+N-1的方法计算图的环复杂度。
辅助线填法如下图所示：

2)多分支判定节点情况

小结

1) 环复杂度有观察法、公式法、判定节点法三种计算方法。
2) 环复杂度的观察法：
在单输入单输出的情况下，根据程序图内部封闭区域数+1的方法得到；在多输出情况下，只有构造强连通图才能使用观察法，此时环复杂度的意义变为强连通图的封闭区域数；也可以认为，多输出需要构造n个辅助线，因而一个输出对应一个多余的外部环数。
3) 环复杂度的公式法：
VF=E-N+2仅适用于单输入单输出的情况下；
VF=E-N+1则适用于任何程序图构造为强连通图之后的情况；程序图改造为强连通图不改变程序图的环复杂度。
4) 环复杂度的判断分支法：
只适用于双分支节点情况，一旦有多分支节点即失效；多分支节点可以用公式法处理，或者将多分支改造为多层双分支层层调用（如果你不嫌累的话）。
5) 环复杂度的通用方法：
是将程序图构造成强连通图然后套用VF=E-N+1公式，简单快捷。构造方法是将输入输出节点相连。

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览35199 人正在系统学习中