Contiguous (USA) State Check

Question

Given a list of States, as in USA States, I am trying to write an algorithm to tell whether or not the States are contiguous. The order does not matter and states can be revisited.

Examples:

• AZ, CA, OR, WA are contiguous
• AZ, CA, NM, UT are contiguous
• AZ, NM, OR, WA are not contiguous

Assumptions:

1. I have a collection of strings that represent the states.

2. I have a collection of state connections.

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

This collection has records in both directions:

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

What have I tried?

Attempt 1: For each state in the collection, check that there is at least one StateConnection with another state in the list.

Why it didn't work? This allows the 3rd example, where there are two separate contiguous ranges to pass.

Attempt 2: Remove states from the list of candidate connecting states after they are checked. This will require a complete path that touches every state once.

Why it didn't work? This does not allow the 2nd example, where one state acts as a hub for multiple states.

I haven't solved any graph theory problems in a while, so I'm a bit rusty.

I am not looking to anything like a shortest path or traveling salesman. I don't care what path is taken or how many moves are used. All I care about whether or not there is a gap.

I'm writing this is C#, but feel free to give an answer in other languages.

Answer 1

Have a look at Flood Filling in graph theory. You would want to "paint" each connected node in your tree and then at the end check if any of your states remain unconnected. It doesn't matter how you traverse the graph to do the painting (BFS or DFS) but this would highlight gaps (or unconnected nodes).