if-statement - 圈复杂度 = 1 + #if 语句？

Question

我发现以下关于圈复杂度的段落on Wikipedia :

It can be shown that the cyclomatic complexity of any structured program with only one entrance point and one exit point is equal to the number of decision points (i.e., "if" statements or conditional loops) contained in that program plus one.

这意味着两个任意嵌套 if 语句的圈复杂度为 3:

if (a)
{
    if (b)
    {
        foo();
    }
    else
    {
        bar();
    }
}
else
{
    baz();
}

由于将调用三个函数中的一个，因此我的直觉同意 3。

但是，两个任意 if 语句也可以按顺序编写而不是嵌套它们:

if (a)
{
    foo();
}
else
{
    bar();
}

if (b)
{
    baz();
}
else
{
    qux();
}

现在有四个路径通过代码:

foo, baz

foo, qux

吧，巴兹

酒吧, qux

因此，这个片段的圈复杂度不应该是 4 而不是 3？

我误解了引用的段落吗？

Answer 1

圈复杂度定义为 的数量。线性独立路径 通过代码。

在您的第二个示例中，我们有以下运行路径...

| # |   A   |    B  |  Nodes hit   |
| 1 | true  | true  |  foo() baz() |
| 2 | true  | false |  foo() qux() |
| 3 | false | true  |  bar() baz() |
| 4 | false | false |  bar() qux() |

您完全正确，这里的执行路径数为 4。但圈复杂度为 3。

关键在于了解圈复杂度的衡量标准:

定义:

A linearly independent path is any path through the program that introduces at least one new edge that is not included in any other linearly independent paths.

来自 http://www.ironiacorp.com/

第 4 条路径与前 3 条路径不是线性独立的，因为它没有引入任何未包含在前 3 条路径中的新节点/程序语句。

如 the wikipedia article 中所述，圈复杂度总是小于或等于理论唯一控制流路径的数量，并且总是大于或等于实际可实现的执行路径的最小数量。

(为了验证第二个语句，想象如果 b == a 是 总是 在输入您描述的代码块时为真)。