独立路径

独立路径是指从程序的入口到出口的多次执行中，每次至少有一个语句是新的，未被重复的，也即每次至少要经历一条从未走过的弧。
独立路径的个数即为环复杂度的个数，而求环复杂度的个数三种方法：
直观观察法：
1.观察程序图将二维平面分割为封闭区域和开放区域的个数。
如图：4个封闭区域和一个开放区域

2.公式计算法：
当终点没有向起点回去时：
V(G) = e (边的个数)- n(顶点个数) + 2;

此时 V(G) = 10 - 7 + 2 = 5

当终点有向起点回去时：
V(G) = e (边的个数)- n(顶点个数) + 1;

此时 V(G) = 11 - 7 + 1 = 5

不管你是不加边公式加2，还是加边公式加1都可以，答案是一样的。

3.判定结点法（节点只有两个分支）
V(G) = 节点数加1：

同样这个图，节点分别为：A、B、C、D 共4个，V(G) = 4 + 1 = 5
无论哪个方法，最后的数是一样的，在这阶段一般是不会出现问题，但在找具体独立路径时，经常有各种疑问：
为什么这条不是独立路径？
为什没这条路径已经覆盖了另一条路径，还拆开做两条路径？
独立路径的集合到底是不是唯一的？

也正是以上各种问题，加上正处疫情阶段，没有课本只能上网课，网络上更是零零散散，找不到标准的、正确的答案，所以写下这个文章，一是希望有专业人士可以找出错误，共同讨论，二是如果有人有同样的疑惑，可以有个参考之处。

看这个图，不管用哪种方法，都可以看出环复杂度也就是独立路径个数为4，
如果找所有路径，可以很简单的看出是2的三次方8个
如果为了覆盖所有路径，那也简单,一共两条路：
e1-e3-e5
e2-e4-e6就够了
这样看好像独立路径和哪个都不沾边，要么少了，要么多了，后来仔细思考，有一个想法，独立路径从所有图的角度来看，是覆盖所有路径的最小数，
独立路径从一个图的角度来看，是覆盖所有路径的最大数。

说的很不专业，也不知道能不能理解我的意思，换一种说法，简单的图如上图，我们可以一眼看出覆盖所有路径的路的最少的个数，但是遇到复杂的图，难道还要一个一个找嘛？我们要找到一个方法，不管图复杂还是简单，我们都可以用这种方法找到覆盖所有路径的个数，也许有重复，但已经把路径的个数从 2 ^ n(节点的个数) 下降到 n(节点的个数)+1了

我们找上图的独立路径个数：
三个节点： A B C
0 0 0
e1-e3-e5
0 0 1
e1-e3-e6
0 1 1
e1-e4-e6
1 1 1
e2-e4-e6
这就是一个独立路径的集合，
向这样找，我们还可以找其他的集合，比如：
三个节点： A B C
0 0 1
e1-e3-e6
0 1 1
e1-e4-e6
1 1 1
e2-e4-e6
1 1 0
e2-e4-e5
只不过这个图特殊，所有的路径组合都能满足，一般的图很多路径组合是无效的，导致独立路径的集合数没那么多。
个人理解，并不专业，有错请说，共同讨论，共同进步。