图形矩阵的问题

tlucia · 发表于 2007-12-21 16:27:00

导出流图和决定基本测试路径的过程均需要机械化，为了开发辅助基本路径测试的软件工具，称为图矩阵(graph matrix)的数据结构很有用。

　　图矩阵是一个正方形矩阵，其大小(即列数和行数)等于流图的节点数。每列和每行都对应于标识的节点，矩阵项对应于节点间的连接(边)，图1-7显示了一个简单的流图及其对应的图矩阵［BEI90］。

　　该图中，流图的节点以数字标识，边以字母标识，矩阵中的字母项对应于节点间的连接，例如，边b连接节点3和节点4。

　　这里，图矩阵只是流图的表格表示，然而，对每个矩阵项加入连接权值(link weight)，图矩阵就可以用于在测试中评估程序的控制结构，连接权值为控制流提供了另外的信息。最简单情况下，连接权值是 1(存在连接)或0(不存在连接)，但是，连接权值可以赋予更有趣的属性：

　　·执行连接(边)的概率。

　　·穿越连接的处理时间。

　　·穿越连接时所需的内存。

　　·穿越连接时所需的资源。