如何確定依賴關係圖解決方案是正確的

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並對它們進行排序。然後訂單總是已知的並且是固定的。在你的情況下，一個接一個地比較相應的節點。