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