public class OrderedDepthFirstSearch<T extends OrderedDfsVertex>
This class guarantees that the vertices will always
be searched in a specific order. To do so, however,
we have to sort the list of all vertices in the graph once,
then each adjacency list that is explored. Due to this overhead,
simple DepthFirstSearch is preferable when the order for
visiting vertices is immaterial to the search.
Prepares the graph for a depth-first search where vertices
are visited in the order specified by the Comparator passed
to this constructor. The constructor does not modify the graph
passed but merely sets up the framework to be used when the
search() method is called.
graph - The graph to be searched
comp - Comparator determining the order in which vertices
will be visited.
If comparator is unspecified, use SearchOrderComparator as the default.
SearchOrderComparator compares vertices on the basis of their search order field.
graph - graph to search
public void search()
Conduct a depth-first search on the graph, visiting vertices
in the order specified in the constructor.
This method modifies the graph in the following ways:
All vertices will be colored black after this method call.
All vertices will have discoveryTime and finishTime set according
to the order in which they were first discovered and finished.
In contrast to the corresponding method in simple DepthFirstSearch,
this search method does not modify the edgeType of the graph's vertices--i.e.,
it does not categorize the edges in the graph. Nor does it return a value
specifying whether or not the graph is cyclic.