[Solved] C# Degree of separation for connected paths [closed]

This can be solved with a breadth first search (BFS) in the graph. This algorithm gives you back a tree whose root is the city you start with and the unique path from there to any other node/city is the one with the fewest possible hops.

If you need this information for all your cities/nodes then run the algorithm once for each city.

For an explanation of BFS and its running time a good source is e.g. wikipedia.

BFS needs a graph as input, preferably given by an adjacency list. The given data thus needs a transformation first: Run over the list and for each city store the cities that are connected directly to it:

Boston: NewYork
NewYork: Boston, Seattle
Seattle: NewYork

Now you maintain three pieces of information: A working queue Q initialized with Boston (in your case), a list S of “already connected” cities initialized with Boston and an array P of “predecessors”: For each city this will contain the previous city on the path from Boston. For Boston this points to nil.

Run over the queue: Pick the first entry c in Q, Run over its adjaceny and whenever you encounter an unconnected city add it to S, set its predecessor to c and add it to the end of Q.

If every city can actually be reached from Boston then you end with a tree of “predecessors”. To determine the distance of a city follow the predecessors from this city to Boston.