测试中的图

——网易云课堂《开发者测试》课程笔记

我们首先介绍如何从软件当中产生图及图的基本定义。图当中，如何去选择它的路径，如何产生测试路径。 曾经有人说过，所谓软件测试，就是把软件变成一张图，然后覆盖它。由此可见，图在软件测试中的重要地位。事实上，图不仅是在软件，应该是计算机里面最常见的一种结构。他已经从最早的计算模型到我们今天计算机里各种各样的图结构。

在软件里面，常见的一种图，可以来自源代码，比我们看这段源代码，它可以转成某种图的结构，那常见的是有控制流图，除了源代码还有各种各样的软件资料可以转换成图结构。比如我们的规格文档，可以转成某种图。常见的有，有限状态机，我们的各种各样的设计图也可以作为我们的测试的一个基础。

首先让我们回顾下什么叫图，大家闭上眼睛，回想一下你可能一年级或者二年级的基础知识。所谓图，是由点和边构成的一个集合。点，又通常称之为顶点或节点，它是一个有穷非空的一个集合。

比如，我们看，我们现在有4个点，我们标记为1、2、3、4，构成一个点的集合。边是来自于点对，比如，我们这4个点，构成有这么4个边，那构成了一个边的集合。由点的集合和边的集合，构成了图。我们可以进一步的规定一个初始节点和终结节点。当然，初始节点和终止节点是集合V的一个子集。 简单的回顾几个小问题，也就是我们刚才定义当中规定点的集合V是有穷非空集合，但并没有规定，边的集合E的特性。那问题就是，第一个，E能不能是空集，也就是单点或者多点，会不会构成一个图。第二个问题就是，边会不会有无穷多个？这两个留给我们课后作业小练习。

还有一些，其他问题我们可以进一步讨论，比如我们刚才的示意是只有一个初始节点，假如，有多个初始节点呢，事实上在我们的程序当中经常有多个初始节点。在这个处理当中我们通常可以通过添加一个哑节点，使它指向所有的初始节点，并把这个哑节点重新规定为一个初始节点，这样就可以归纳为只有一个初始节点。同样的道理，我们假设有多个终结节点段时候，也可以通过添加哑节点段方式，使得最终只有一个终结节点。所以在这门课当中，我们限制只有一个初始节点和一个终结节点，这并不影响我们的表达能力。接下来让我们理解图中的一个重要概念，路径。路径是指一个点的序列，它当然要求，相邻的两个点构成一个有效边，也就是属于E这个集合。

让我们首先来看一下这张图，这是一个典型的双菱形结构，也是我们程序当中很常见的一种结构。那么这里面1-2-4-6是构成了一个有效路径，而1-2-3-4，在2和3之间并不是一个有效边，所以它不是一条路径，我们可以进一步规定路径的一些特性，比如，路径的长度，我们以边的数量来定义路径的长度，单点是一个特殊的路径，它的长度为零，一个路径是另外一个路径的子路径。是指它是它的子序列。比如我们看刚才的这张图，1-2-4-6，是一条路径，它的长度为三，2-4-6是1-2-4-6的一个子路径，它长度为二，而，1-2-6并不是1-2-4-6的子路径，因为它中间已经被断开了。我们前面讲的是图的基本知识，那它跟我们测试有什么关系？

在这门课当中，我们定义测试路径是一条从初始节点到终结节点之间的这么一条路径。比如刚才的这张双菱形结构图，我们看一下他有多少路径？这个需要大家掰着手指头可能都算不出来。每个单点是一个路径，每个边也是一个路径，边对可以进一步扩展长度为二的路径，一直可以通过写一个遍历算法输出来。这个图至少有几十条路径，但他的测试路径只有四条，因为他必须从1开始到7结尾。

在软件测试当中，测试路径是用来表达测试的执行，我们需要注意的是，相同的一条测试路径可能会被不同的测试执行到。也就是有多种不同的测试输入，他们执行到的测试路径是一样的。还特别需要注意的是，有些测试路径，是不可行的。也就是它不能被任何测试输入所执行到，这个大家需要细想一下。 第一个，我们如何来展现一条测试路径被多个测试执行到，只要构造出不同的测试输入使得他们执行的路径相同即可。第二个问题就难很多，我们怎么去证明一条测试路径不能被任何测试执行到？很不幸，这是一个不可判定的问题，也就是我们没有办法去证明这条测试路径，不能被任何测试执行到。我们后面会讲到，这点会给我们的测试带来极大的挑战。后面的练习，我们可以按照这个图结构去构造这么一个程序，并且迫使他其中有一条路径不能被任何测试执行。 我们进一步来讲解测试和测试路径之间的关系，我们刚才提到，一条测试，他仅仅能执行一条测试路径，这在确定性环境的时候是这样的情况，当然在非确定性程序，相同的一条测试在不同的时候它执行的测试路径可能不同，但这不在我们这门课当中，也就是我们这门课规定，一条测试只能执行一条测试路径。所以我们用path(t)来代表测试t所执行的这么一条测试路径，我们用path(T)来代表测试用例集T里面所有的测试用例执行到的测试路径集合。

这就是测试和图的一些基本概念，它将为我们后面几节的测试方法奠定一个重要的基础。