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

interface DictionaryInterface . The method is not public, as we will call it only from
methods declared in GraphAlgorithmsInterface .
protected void resetVertices()
{

Iterator<VertexInterface<T>> vertexIterator = vertices.getValueIterator();
while (vertexIterator.hasNext())
{

VertexInterface<T> nextVertex = VertexIterator.next();
nextVertex.unvisit();
nextVertex.setCost(0);
nextVertex.setPredecessor( null );
} // end while
} // end resetVertices

Question 4 Create an instance of the class DirectedGraph for the graph described in
Question 3.

29.22

Efficiency. Adding a vertex to a graph is an O( n ) operation, since the vertex is added to a linked
dictionary. Adding an edge involves retrieving two vertices from the dictionary and then calling
Vertex 's method connect . Thus, the method addEdge is also O( n ). Likewise, hasEdge is O( n ), as it
first retrieves two vertices from the dictionary. It then iterates through the edges that leave the first
vertex to see whether one of them ends at the second vertex. As you can see, the performance of
these three graph operations depends on the number of vertices in the graph. The remaining meth-
ods in BasicGraphInterface are each O(1). Figure 29-4 summarizes these observations.

FIGURE 29-4

The performance of basic operations of the ADT graph when
implemented by using adjacency lists

O( n )
O( n )
O( n )
O( 1 )
O( 1 )
O( 1 )
O( 1 )

addVertex
addEdge
hasEdge
isEmpty
getNumberOfVertices
getNumberOfEdges
clear

Graph Algorithms
29.23

Breadth-first traversal. Segment 28.12 of the previous chapter presented an algorithm for a
breadth-first traversal of a nonempty graph, beginning at a given origin vertex. Recall that the tra-
versal first visits the origin and the origin's neighbors. It then visits each neighbor of the origin's
neighbors. The traversal uses a queue to hold the vertices as they are visited. The traversal order is
the order in which vertices are added to this queue. But since the algorithm must remove vertices
from this queue, we maintain the traversal order in a second queue. Since this second queue is
returned to the client, we enqueue vertex labels instead of vertices. Remember that the class Vertex
is unavailable to the client.