圖形問題的算法

Question

我需要檢查列表中方向節點的連通性。 基本上每個問題有2至7個答案。選擇的答案決定了下一個問題。 因爲這些對將被手動捕獲，所以我需要檢查每個可能的迴路（不允許）和死路（所有路徑必須停在END節點） 任何指針？

start --> n1 --- n2 --- n3 --- n4 --- end 

      \/ \  \ / /

      n5  \  n6------ n7 

       \  \ / /

       n8----n9---n10----n11 

      DIRECTION --> 

Answer 1

這可能是你在找什麼：

Testing whether a graph is acyclic

你的最終節點是葉子節點是在該網頁的術語是什麼。

1. 如果圖沒有節點，則它是非循環的。
2. 如果圖沒有葉，它是循環的。
3. 選擇任何葉子，去掉葉和所有過渡到它，轉到步驟1

要檢查有沒有死角：只要保證只有使用上述算法之前單一的葉節點。

Answer 2

使用breadth first search算法，跟蹤您已經訪問過的所有節點。如果在搜索要遍歷的下一個節點時，其中一個已經訪問過的節點是可能的，那麼該圖是錯誤的。此外，如果您到達的節點沒有其他可能的節點要遍歷到下一個節點，並且尚未達到最終結果，那麼該圖形也沒有正確連接。