連續（美國）州檢查

Question

給出一個國家名單，如美國國家，我試圖寫一個算法來說明這些州是否是連續的。順序無關緊要，狀態可以重新訪問。

實例：

• AZ, CA, OR, WA是鄰接
• AZ, CA, NM, UT是鄰接
• AZ, NM, OR, WA是不連續的

假設：

1. 我有一個代表狀態的字符串集合。

2. 我有一個狀態連接的集合。

   class StateConnection 
   { 
       public string OriginState { get; set; } 
       public string ConnectingState { get; set; } 
   } 
   

該集合在兩個方向記錄：

• OriginState = AZ, ConnectingState = CA
• OriginState = CA, ConnectingState = AZ

我有什麼企圖？

嘗試1： 對於集合中的每個狀態，檢查是否至少有一個StateConnection與列表中的另一個狀態。

爲什麼它不起作用？ 這允許第三個示例，其中有兩個單獨的連續範圍要通過。

嘗試2： 檢查後，從候選連接狀態列表中刪除狀態。這需要一個完整的路徑來觸及每個狀態一次。

爲什麼它不起作用？ 這不允許第二個例子，其中一個狀態充當多個狀態的中心。

我在一段時間內還沒有解決任何圖論問題，所以我有點生疏。

我不期望像最短路徑或旅行推銷員。我不在乎採取了什麼路徑或者使用了多少步驟。我只關心是否存在差距。

我正在寫這是C＃，但隨意給其他語言的答案。

Answer 1

這聽起來像是最好的解決方案只是通過狀態圖的廣度優先搜索。類似（使用第一個列表作爲示例）：

• 創建要檢查的狀態隊列。首先，它是空的。
• 在列表中選擇一個狀態，例如CA，將其添加到隊列中。

然後循環如下：

• 出列從隊列的狀態。標記爲已粘貼。
• 檢查是否有任何直接的鄰居（沒有被訪問過）在列表中。如果是，請將它們添加到隊列中。
• E.g.在CA的情況下，我們在列表中發現兩個neighbours：OR和​​;將它們添加到下一個待檢查狀態的隊列中。稍後，當檢查OR時，我們會看到WA和CA是它的鄰居並且在列表中;但CA已被訪問，因此我們只會將WA添加到要訪問的州的列表中。

繼續，直到沒有更多的狀態出隊。如果我們在那個點上訪問了最初列表中的所有狀態，那麼這個列表是連續的。否則它不是。

Answer 2

查看圖理論中的Flood Filling。你會想要在你的樹中「繪製」每個連接的節點，然後檢查你的狀態是否保持未連接狀態。如何遍歷圖形來完成繪製（BFS或DFS）並不重要，但這會突出顯示間隙（或未連接的節點）。

Answer 3

創建狀態中的所討論的子集的連接矩陣（即包括行和對於子集中的每個狀態的列的N*N布爾矩陣，m[i,j]==true當且僅當狀態i和j是彼此相鄰） 。

運行下面的算法：

for (int k=0 ; k != N ; k++) 
    for (int i=0 ; i != N ; i++) 
     for (int j=0 ; j != N ; j++) 
      m[i,j] |= (m[i,k] && m[k,j]); 

驗證的m[i,j]所有元素都設置爲true三個環路完成後。如果任何元素是false，則狀態不是連續的。

如果您忘記了什麼是「那個三迴路的東西」，它是着名的Floyd-Warshall algorithm尋找傳遞閉包的圖。