连续（美国）州检查

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寻找传递闭包的图。