51Testing软件测试论坛

标题: 关于圈复杂度（或称环路复杂度）的疑问 [打印本页]

作者: sunok 时间: 2004-10-13 09:17
标题: 关于圈复杂度（或称环路复杂度）的疑问
近期在学习《软件测试》，Paul C. Jorgensen的那本书，
书中提到圈复杂度的概念。
我同时参考了其他人的几本书，也都提到了类似概念，即环路复杂度，
但他们的计算公式各不相同，我被弄糊涂了。
还望各位高手指点一哈子。多谢多谢！

一种典型公式为：V(G)=e-n+p
作者又说，V(G)=e-n+2p，通过增加从汇节点到源节点的一条边即可，
但如果该图中存在多个组件，则无法按照这种方式来计算。
第三种方法是：计算中图中判定节点的个数，设为n，则V(G)=n+1，
第四种方法：通过构造相邻矩阵计算，其实质是计算所有节点的出度的和，并减去节点总数，就是圈复杂度的大小。
第四种方法：直接根据图中的边将整个图的平面分割成的区域数来决定V(G)。
不同方法的计算结果往往是不同的。

另外，对于图中边和节点的处理，也不同。
比如：结构化程序设计构造的有向图中，关于前测试环路，即while...dol模式，书中给出的图包含2个节点，4条边，而另外的书中给出的图则包含3各节点，3条边，由于图不同，得到的圈复杂度也不同。

我的理解是：V(G)=e-n+p是个通用的公式，
当碰到连通图时，（反正我们在进行程序分析时，通常图中是只有一个组件的），就通过构造强连通，并利用V(G)=e-n+2p来计算。
而其它公式，保险的情况下，适用于单个源节点和单个汇节点的连通图情况。

是这样的吗？还是有别的什么考虑？请多指教呀！

作者: sunok 时间: 2004-10-13 09:18
我们在从程序构造图的时候，是不是一定要从节点开始，节点结束，而不能从边开始或结束？否则计算得到的圈复杂度是错误的？

作者: easycan 时间: 2007-10-22 16:49
今天刚刚遇到一个测试得笔试题，怎么理解圈复杂度？我都没做~~呜呜~~

欢迎光临 51Testing软件测试论坛 (http://bbs.51testing.com/)