4

给定一个州列表，就像在美国州一样，我正在尝试编写一个算法来判断这些州是否是连续的。顺序无关紧要，可以重新访问状态。

例子：

  • 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#，但请随时用其他语言给出答案。

4

3 回答 3

4

看看图论中的洪水填充。您可能希望“绘制”树中的每个连接节点，然后在最后检查您的任何状态是否保持未连接。无论您如何遍历图形来进行绘画（BFS 或 DFS），但这会突出显示间隙（或未连接的节点）。

于 2012-07-27T15:02:41.977 回答
2

听起来最好的解决方案只是通过状态图进行广度优先搜索。类似于（以第一个列表为例）：

  • 创建要检查的状态队列。一开始，它是空的。
  • 选择列表中的一个状态，例如CA，将其添加到队列中。

然后循环如下：

  • 从队列中取出一个状态。将其标记为已访问。
  • 检查它的任何直接邻居（尚未访问过的）是否在列表中。如果是，请将它们添加到队列中。
  • 例如，在 的情况下CA，我们在列表中找到了两个邻居：OR和AZ; 将它们添加到要检查的下一个状态队列中。稍后，在检查 时OR，我们会看到WA和CA是它的邻居并且在列表中；但CA已经被访问过，所以我们只会添加WA到要访问的状态列表中。

继续，直到没有更多的状态可以出队。如果到那时我们已经访问了初始列表中的所有状态，那么该列表是连续的。否则不是。

于 2012-07-27T15:04:45.830 回答
2

创建相关状态子集的连接矩阵（一个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 算法，用于寻找图的传递闭包。

于 2012-07-27T15:04:48.773 回答