Data Structures: Traversing a Graph

Let's say we want to find the path between an origin and a destination in a graph.  We'll want to return a LinkedList that lists vertices in order from the origin to the destination.  To do this we’ll find the shortest path.

In order to implement a getShortestPath method, we can take the following steps:

1. Create a queue.  This will tell you the next vertices to visit.
2. Create a map.  This will allow you to identify visited vertices, as well as trace your path backward.
3. Add the origin vertex to your queue.
4. Add the origin vertex to your map (try origin as the key, and null as the value).
5. Then, while your queue is not empty (i.e. while you still have nodes not traversed):
1. Retrieve & remove the next value from your queue.  We’ll call it “currentVertex” for now.
2. If currentVertex is your destination, you’ve finished.  Calculate the path from origin to destination (using your map) and return it.
3. If currentVertex is not your destination, retrieve the vertices adjacent to it.  
1. We can call each of these neighbor vertices “neighborVertex” for now.
2. If neighborVertex is not a key in your map, then add it to the queue.
3. Also, if neighborVertex is not a key in your map, add it to your map (where the map keys are neighborVertex, and the map values are currentVertex).
4. If your queue is empty, that means you’ve looked at all of the vertices. There’s no path from origin to destination, so return null.

The procedure for calculating the path from origin to destination is pretty easy once you’ve found the destination and you have a map (where the keys are vertices, and their values are how you traveled to that vertex).

1. Create a variable called “current” and set it equal to your destination.
2. Create a LinkedList to represent the path.
3. While current is not your origin:
1. Add current to the front of your list.
2. Retrieve the value for current from the map.
3. Set current equal to that value.
4. Add origin to the front of your list.

Note that there may be 2 or more shortest paths from origin to destination in your graph - that’s OK and not entirely unexpected.

Consider this graph:

If we are trying to find the shortest path from A to F, we start with an empty queue and an empty map.

• map: {}
• queue: 

We start by adding the origin to our queue, and identify in our map that it came from "nowhere" - i.e., it's where we're starting.

• map: {A => null}
• queue: A

Then we start step 3.  We take A from the queue:

• map: {A => null}
• queue: 
• currentVertex: A

A is not our destination, so we proceed to check the neighbors of A.  None of them are in our map, so we add them to the queue and the map:

• map: {A => null, B => A, D => A}
• queue: B, D
• currentVertex: A

Now we retrieve and remove the front of our queue:

• map: {A => null, B => A, D => A}
• queue: D
• currentVertex: B

B is not our destination, so we proceed to check the neighbors of B. B’s neighbors are A, C, and F.  A and B are already keys in our map, so we add F to the queue and the map:

• map: {A => null, B => A, D => A, F => B}
• queue: D, F
• currentVertex: B

Now we retrieve and remove the front of our queue again:

• map: {A => null, B => A, D => A, F => B}
• queue: F
• currentVertex: D

D is not our destination, so we proceed to check the neighbors of D. D’s neighbors are A and E.  A is already a key in our map, so we add E to the queue and the map:

• map: {A => null, B => A, D => A, E => D, F => B}
• queue: F, E
• currentVertex: D

Now we retrieve and remove the front of our queue again:

• map: {A => null, B => A, D => A, E => D, F => B}
• queue: E
• currentVertex: F

F is our destination, so we retrieve the values from a map and build a Linked List.  We start with current = F.

• map: {A => null, B => A, D => A, E => D, F => B}
• current: F
• list: 

We add F to the beginning of the list, then retrieve the value of F from the map and get B and set current to B.

• map: {A => null, B => A, D => A, E => D, F => B}
• current: B
• list: F

We add B to the beginning of the list, then retrieve the value of B from the map and get A.

• map: {A => null, B => A, D => A, E => D, F => B}
• current: A
• list: B => F

Our destination is A, so we are done looping.  We just need to add A to the beginning of our list.  We end up with this:

• map: {A => null, B => A, D => A, E => D, F => B}
• current: A
• list: A => B => F

ABF is the shortest path.

You can try this approach with any two vertices in your graph - if any path exists between them, this algorithm will find the shortest path.  If you’re not sure - try working out the algorithm on paper for origin=A and destination=G.  There are 3 possible paths from A to G; ABCFG, ABFG, and ADEHG.  This algorithm will find the shortest (ABFG).