Java Reference
In-Depth Information
Although adding to a list can be done in O(1) time, scanning the list to prevent duplicate edges
takes more time. Since each vertex in a graph of n vertices can be the origin of at most n 1 edges,
connect is an O( n ) operation. For a sparse graph, however, the number of edges originating at any
vertex is much less than n . In this case, connect is significantly faster than O( n ).
29.13
The iterators. The method getNeighborIterator returns an iterator to a vertex's adjacent vertices,
that is, its neighbors. We define a private inner class— neighborIterator —within Vertex that imple-
ments Java's interface Iterator . Thus, getNeighborIterator has the following implementation:
public Iterator<VertexInterface<T>> getNeighborIterator()
{
return new neighborIterator();
} // end getNeighborIterator
The class neighborIterator appears in Listing 29-4. Its constructor establishes an instance of
the iterator defined in LinkedListWithIterator . The method next uses this iterator to traverse the
edges in the vertex's adjacency list. Then, using Edge 's method getEndVertex , next accesses the
neighboring vertex and returns it.
LISTING 29-4
The private class neighborIterator , as an inner class of Vertex
private class neighborIterator implements Iterator<VertexInterface<T>>
{
private Iterator<Edge> edges;
private neighborIterator()
{
edges = edgeList.getIterator();
} // end default constructor
public boolean hasNext()
{
return edges.hasNext();
} // end hasNext
public VertexInterface<T> next()
{
VertexInterface<T> nextNeighbor = null ;
if (edges.hasNext())
{
Edge edgeToNextNeighbor = edges.next();
nextNeighbor = edgeToNextNeighbor.getEndVertex();
}
else
throw new NoSuchElementException();
return nextNeighbor;
} // end next
 
Search WWH ::




Custom Search