1. 环复杂度

1.1 环复杂度的概念与计算

首先我们来了解一种对程序的复杂度进行度量的方法，环复杂度度量。这种度量方法取名自软件工程早期年代一位比较活跃的科学家 Thomas ·Mike，他提出的这种程序复杂度的度量方法非常直观。

我们来考虑一下什么样的程序是简单的程序，什么样的程序是复杂的程序。如果一个程序当中没有任何分支，没有任何循环，我们肯定认为这样的程序是简单的，因为它的执行路径是唯一的。那么如果程序当中有分支有循环，这个程序就会变得比较复杂。

如果程序当中的分支循环非常多，那么这个程序它的复杂性当然也会非常高，所以程序的复杂度，我们可以用程序当中分支和循环的数量来体现。

Mike 所提出的这种复杂度的度量方法，首先需要我们获得程序的控制流图，我们需要去数一下这个程序的控制流图当中有多少个节点，有多少条边，然后边的数量减去节点的数量加二，就是环复杂度度量值。

✅ 结论：环复杂度 = 边的数量 – 节点数量 + 2

1.2 环复杂度计算实例

我们考虑上一篇文章中给出的两个例子。第一个是三角形形状判断程序：

这个例子里，程序的控制流图当中有 7 个结点 8 条边（指向起始节点的边不计入），所以说它的环复杂度的值是 8 – 7 + 2 = 3。

下面是对 vector 容器中数据统计并求方差的程序：

这个程序中有两个循环，控制流图中有 9 个节点 10 条边，所以环复杂度为 10 – 9 + 2 = 3。

1.3 其他的环复杂度计算方法

那么环复杂度度量还有没有别的计算方法？其实有一些更简单的方法，我们之所以称这种度量方法为环复杂度度量，是因为我们可以在控制流图当中去数控制流图当中有多少个环。

我们看 vector 容器中数据统计并求方差的程序，其控制流图当中有 2 个环，那么环的数量加 1，就是环复杂度度量的值，为 3。

我们再来看三角形程序当中，控制流图也是有 2 个环，那么 2+1 也是环复杂度度量的值。

那么环的数量到底意味着什么？我们可以思考一下，在控制流图当中什么时候会出现环？只有当控制流图当中出现了分支或者循环的时候，控制流图当中才会出现环，也就是一个被封闭起来的区域。一般来说有一条谓词语句，那么它就会对应的有一个环。所以这种复杂度在做计算的时候，我们也可以采用第三种方法，就是去数一下程序当中有多少个谓词语句。那么谓词语句的数量加一也等于环复杂度度量的值。

✅ 结论：环复杂度 = 环的数量/谓词语句 + 1

---

2. 基本路径测试

环复杂度度量值算出来之后对我们有什么用呢？这就需要独立路径的概念了。

2.1 独立路径的概念

独立路径是控制流图当中一条从起始节点到终止节点的路径，这条路径相对于其他的路径需要包含一些此前没有被覆盖过的点或者边，那么这条路径我们就称之为它是一个独立路径 。你也可以理解为，和其他的独立路径相比，至少引入一个新处理语句或一个新判断的程序通路。一般来说环复杂度度量值，它就是一个程序当中独立路径数量的上限。

我们以三角形程序为例，通过刚才的控制流图，我们已经计算得到它的环复杂度度量值是 3。我们当然可以找到三条独立路径，分别是 ：

• 1 → 2 → 7
• 1 → 3 → 4 → 6 → 7
• 1 → 3 → 5 → 6 → 7

我们注意这三条路径，每一条路径相对于其他路径都是独立路径。

然后我们再看另外一个控制流图，就会发现一些不一样的情况。

在这个控制流图当中，我们看两条路径：

• 1 → 2 → 3 → 5 → 6 → 7 → 9
• 1 → 2 → 3 → 4 → 3 → 5 → 6 → 7 → 8 → 7 → 9

那么分别对应循环体，不执行和循环体各执行一次这两种情况。这里我们会发现路径二相对于路径一是独立的，因为在路径二当中出现了路径一当中没有出现的两个节点分别是节点 4 和节点 8，而路径一相对于路径二它就不是独立的。

这个例子告诉我们，路径独立与否，它是一个相对的概念，了解过环复杂度和独立路径这两个概念之后，我们来看如何进行基本路径测试。

2.2 基本路径测试

在进行基本路径操作的时候，我们要进行 4 步操作：

1. 生成控制流图
2. 计算它的环复杂度
3. 选择一个独立路径的集合
4. 针对每一条独立路径生成测试用例

针对下面这个例子，我们已经计算过环复杂度为 3 。所以我们首先尝试寻找三条独立路径，分别是：

• 1 → 2 → 3 → 5 → 6 → 7 → 9
• 1 → 2 → 3 → 4 → 3 → 5 → 6 → 7 → 9
• 1 → 2 → 3 → 5 → 6 → 7 → 8 → 7 → 9

很显然这三条路径，那么路径二相对于路径一是独立的，路径三相对于路径一和路径二也是独立的，那么它可以构成一个基本路径的集合，但是这三条路径可以用来测试吗？

答案是不行，为什么？因为我们注意到在这个程序当中两个循环，它们的功能都是对这个 vector 进行遍历，那么 vector 的长度直接决定了循环体执行的次数，所以说两个循环体它们执行的次数应该是相等的。而在这里的路径二和路径三当中，两个循环体执行的次数不相等，所以说这两条路径它并不是一个合法的可执行的路径，所以说这一组路径我们不能使用。

✅ 结论：基本路径的选择要合法可执行

好，接下来我们再尝试寻找另外一组独立路径的集合，那么首先是第一条路径，1 → 2 → 3 → 5 → 6 → 7 → 9，即两个循环体都不执行。

第二条路径，1 → 2 → 3 → 4 → 3 → 5 → 6 → 7 → 8 → 7 → 9，也就是两个循环体各执行了一次，很显然路径二相对于路径一是独立的，那么这个时候我们得到了一个包含两条路径的基本路径集合。接下来我们针对两条可执行的路径来分别设计测试用例。那么第一条测试用例 numbers 这样一个容器，它里面不包含任何元素，而第二条测试用例 numbers 这样一个容器当中只包含 1 个元素，我们不妨令它为 1，这样我们就完成了基本路径测试。