c# - 连续(美国)状态检查

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

看看Flood Filling在图论中。您可能想要“绘制”树中每个连接的节点，然后在最后检查您的任何状态是否保持未连接状态。您如何遍历图形来进行绘画(BFS 或 DFS)并不重要，但这会突出显示间隙(或未连接的节点)。