如何确定依赖关系图解决方案是正确的

Question

我创建了一个类，该类使用有向图，该图中的一个顶点，并输出一个可接受的顶点序列以通向该顶点。

例如

• A-> B
• A->Ç
• B-> d
• C-> d

两个顶点d可能序列是：

• A-> B-> C-> D
• A-> C-> B-> D

现在，我需要设计一个测试来确定我的程序给出的解决方案是否正确。

任何想法？

Answer 1

你可以使用基于Cyclomatic Complexity的算法来计算应该可以找到的路径的数量，这将是一个很好的完整性检查 - 尤其如果你有一个非常大的图形，恰好有路径的权数会让人放心的（尽管不是保证路径本身是正确的！）。广义而言，边数减去节点数 - 您会在维基百科页面上看到细微差别。

Answer 2

你的问题很常见。基本上有两个类似的，简便的方法来处理它：

• 把节点的序列中的一组和检查组的大小，以及是否包含了所有的序列

• 根据序列排序一些已知的算法（例如通过比较一个接一个节点）。现在订单总是一样的。

在Java中，这将意味着：

• 实施equals和hashCode为节点的顺序（如果这是一样的东西List<Node>，落实Node代替equals和hashCode），并把它们放在HashSet 。然后，只需检查该集合是否具有正确的大小并包含两个路径。

• 制作节点序列Comparable并对它们进行排序。然后订单总是已知的并且是固定的。在你的情况下，一个接一个地比较相应的节点。