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: 
It sounds like the best solution would be just a breadth-first search through the graph of states. Something like (using the first list as an example):

* Create a queue of states to examine. To start, it is empty.
* Pick the a state on the list, e.g. `CA`, add it to the queue.

Then loop as follows: 

* Dequeue a state from the queue. Mark it off as visisted.
* Check whether any of its immediate neighbours (that have not been visited) are on the list. If yes, add them to the queue.
* E.g. in case of `CA`, we found two neightbours on the list: `OR` and `AZ`; add them to a queue of next states to examine. Later, when examining `OR`, we'll see that `WA` and `CA` are its neighbours and are on the list; but `CA` was already visited, so we'll only add `WA` to the list of states to visit.

Continue until there are no more states to dequeue. If we've visited all states on the initial list by that point, then the list is contiguous. Otherwise it's not.
Create a connectivity matrix of the subset of states in question (a `N*N` boolean matrix that includes a row and a column for each state in the subset, with `m[i,j]==true` if and only if states `i` and `j` are adjacent to each other).

The run the following algorithm:

```
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]);

```

Verify that all elements of `m[i,j]` are set to `true` after the three loops finish. If any element is `false`, the states are not contiguous.

In case you have forgotten what is "that three-loop thing", it's the famous [Floyd-Warshall algorithm](http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) for finding transitive closures of graphs.