JURUO怎么写 qwertier's blog

自动生成白盒测试基本路径

题目链接:https://cms.hit.edu.cn/mod/assignment/view.php?id=8919

注意事项有四条:

  1. 在查找基本路径时,采用深度优先搜索策略;若遇到判定节点,需遵循“先遍历false分支,再遍历true分支”的原则。
  2. 若某一条路径出现循环,即:该路径的后续部分已经在本路径之前出现过,则在进入循环的第一个节点处停止,后续部分不需要再包含在该路径中(例如1,2,3,9,10,2,3这样的路径,需简化为1,2,3,9,10,2即可)。
  3. 需根据“基本路径”的定义对每一条路径进行检查,看其中是否包含了之前其他路径中不曾出现过的边。若否,则将其去除;
  4. 若程序需要输出多条基本路径,按照路径长度由小到大排序输出;若两个路径的长度相等,则按相对应位置的数字大小由低到高排列(例如1,3,6,5和1,3,4,5两条路径,后者应该先输出;1,10,8,3,4和1,9,10,3,4两条路径,后者应该先输出)。

值得注意的是,第二条中应该改为当某条路径遇到这条路径之前访问过的节点时,停止访问。

我们先不考虑扩展要求,那么就可以得到一个简单的算法:

DFS(u):
    if vis[u] = True 或者 u无出边
        找到一条路径
        return
    vis[u] = True
    按照先F分支后T分支的顺序遍历u的出边,设当前边指向的节点为v
        DFS(v)
    vis[u] = False

考虑扩展需求之后,加边时就有一点小trick。

图片1

图片2

如果是AND关系,那么就会如上面两个图,靠上的图是分裂之前的样子,靠下的图是分裂之后的样子。

可以看出所有指向2的节点现在需要指向2.1,所以我们可以给每个节点设一个节点对应的值。先不考虑扩展需求,生成图。然后把原来2号节点的值从2设为2.1,然后新建一个节点2.2,然后修改他们指向的边就可以了。

这样这个题就完成了,逻辑比较简单,代码也不长(100+)。