Graph Implementations - Data Structures and Abstractions with Java - page 772

The following implementation of the method getBreadthFirstTraversal closely follows the
pseudocode given in the previous chapter. The parameter origin is an object that labels the origin
vertex of the traversal.
public QueueInterface<T> getBreadthFirstTraversal(T origin)
{

resetVertices();
QueueInterface<T> traversalOrder = new LinkedQueue<T>();
QueueInterface<VertexInterface<T>> vertexQueue =
new LinkedQueue<VertexInterface<T>>();
VertexInterface<T> originVertex = vertices.getValue(origin);
originVertex.visit();
traversalOrder.enqueue(origin); // enqueue vertex label
vertexQueue.enqueue(originVertex); // enqueue vertex
while (!vertexQueue.isEmpty())
{

VertexInterface<T> frontVertex = vertexQueue.dequeue();
Iterator<VertexInterface<T>> neighbors =
frontVertex.getNeighborIterator();

while (neighbors.hasNext())
{

VertexInterface<T> nextNeighbor = neighbors.next();
if (!nextNeighbor.isVisited())
{

nextNeighbor.visit();
traversalOrder.enqueue(nextNeighbor.getLabel());
vertexQueue.enqueue(nextNeighbor);
} // end if
} // end while
} // end while
return traversalOrder;
} // end getBreadthFirstTraversal

The implementation of a similar method to perform a depth-first traversal is left as an exercise.

Question 5 Write Java statements that display the vertices in a breadth-first traversal of
the graph that you created in Question 4, beginning with vertex A .

29.24

Shortest path. The shortest path of all paths from one vertex to another in an unweighted graph is
the path that has the fewest edges. The algorithm that finds this path—as you saw in Segment 28.19
of the previous chapter—is based on a breadth-first traversal. When we visit a vertex v , we mark it
as visited, note the vertex p that precedes v in the graph, and note the length of the path that the tra-
versal followed to reach v . We place both this path length and a reference to p into the vertex v .
When the traversal reaches the desired destination, we can construct the shortest path from this data
in the vertices.
The implementation of the method getShortestPath closely follows the pseudocode given in
the previous chapter. The parameters begin and end are objects that label the origin and destination
vertices of the path. The third parameter path is an initially empty stack. At the conclusion of the
method, this stack contains the labels of the vertices along the shortest path. The method returns the
length of this path.