com.codemelon.graph.algorithm.search

Class DepthFirstSearch<T extends DfsVertex>

java.lang.Object

com.codemelon.graph.algorithm.search.DepthFirstSearch<T>

public class DepthFirstSearch<T extends DfsVertex>
extends java.lang.Object

This is the most basic implementation of depth-first search. Only discovery and finish times are determined. It follows CLRS, p. 604. The graph to be searched may be directed or undirected.

Constructor Summary

Constructors

Constructor and Description
DepthFirstSearch(AbstractGraph<T> graph) Prepare the depth-first search.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	search() Conduct a depth-first search on the graph, visiting vertices in no predetermined order.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DepthFirstSearch

public DepthFirstSearch(AbstractGraph<T> graph)

Prepare the depth-first search. No changes are made to the graph when it is passed into the constructor.

Parameters:

graph - graph on which the search will be run

Method Detail

search

public boolean search()

Conduct a depth-first search on the graph, visiting vertices in no predetermined order. This method modifies the graph in the following ways:

1. All vertices will be colored black after this method call.
2. All vertices will have discoveryTime and finishTime set according to the order in which they were first discovered and finished. The first discovery time will be 0.

The search() method returns a boolean value which is true iff the graph is acyclic.

Returns:

true iff the graph is acyclic.