com.mhhe.clrs2e
Class DFS

java.lang.Object
  |
  +--com.mhhe.clrs2e.DFS

Direct Known Subclasses:

SCC.FirstDFS, SCC.SecondDFS, TopoSort.TopoSortDFS

public class DFS

extends java.lang.Object

Class that performs a depth-first search on a graph. Based on DFS code on page 541 of Introduction to Algorithms, Second edition.

Field Summary

protected com.mhhe.clrs2e.DFSInfo[]	dfsInfo Array of DFSInfo objects, one per vertex, to hold the result of the depth-first search.
protected int	time The global timestamp.

Constructor Summary

DFS()

Method Summary

protected void	dfsVisit(com.mhhe.clrs2e.AdjacencyListGraph g, com.mhhe.clrs2e.Vertex u) Performs a depth-first search on a graph starting from a given vertex, filling in discovery times, finish times, and parents in the predecessor graph in the dfsInfo array.
protected void	discover(com.mhhe.clrs2e.AdjacencyListGraph g, com.mhhe.clrs2e.Vertex u) Performs an action upon discovering a vertex in a graph.
protected void	finish(com.mhhe.clrs2e.AdjacencyListGraph g, com.mhhe.clrs2e.Vertex u) Performs an action upon finishing a vertex in a graph.
com.mhhe.clrs2e.DFSInfo	getDFSInfo(int v) Returns a reference to the DFSInfo object for a given vertex.
com.mhhe.clrs2e.DFSInfo	getDFSInfo(com.mhhe.clrs2e.Vertex v) Returns a reference to the DFSInfo object for a given vertex.
void	search(com.mhhe.clrs2e.AdjacencyListGraph g) Performs a depth-first search on a graph from a given source vertex, filling in discovery times, finish times, and parents in the predecessor graph in the dfsInfo array.

Methods inherited from class java.lang.Object

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

Field Detail

time

protected int time

The global timestamp.

dfsInfo

protected com.mhhe.clrs2e.DFSInfo[] dfsInfo

Array of DFSInfo objects, one per vertex, to hold the result of the depth-first search.

Constructor Detail

DFS

public DFS()

Method Detail

search

public void search(com.mhhe.clrs2e.AdjacencyListGraph g)

Performs a depth-first search on a graph from a given source vertex, filling in discovery times, finish times, and parents in the predecessor graph in the dfsInfo array.

Parameters:

g - The graph.

dfsVisit

protected void dfsVisit(com.mhhe.clrs2e.AdjacencyListGraph g,
                        com.mhhe.clrs2e.Vertex u)

Performs a depth-first search on a graph starting from a given vertex, filling in discovery times, finish times, and parents in the predecessor graph in the dfsInfo array.

Parameters:

g - The graph.

u - The vertex being searched from.

getDFSInfo

public com.mhhe.clrs2e.DFSInfo getDFSInfo(com.mhhe.clrs2e.Vertex v)

Returns a reference to the DFSInfo object for a given vertex.

Parameters:

v - The vertex for which the corresponding DFSInfo is returned.

getDFSInfo

public com.mhhe.clrs2e.DFSInfo getDFSInfo(int v)

Returns a reference to the DFSInfo object for a given vertex.

Parameters:

v - The index of the vertex for which the corresponding DFSInfo is returned.

discover

protected void discover(com.mhhe.clrs2e.AdjacencyListGraph g,
                        com.mhhe.clrs2e.Vertex u)

Performs an action upon discovering a vertex in a graph. This method does nothing and is designed to be overridden in subclasses.

Parameters:

g - The graph.

u - The vertex just discovered.

finish

protected void finish(com.mhhe.clrs2e.AdjacencyListGraph g,
                      com.mhhe.clrs2e.Vertex u)

Performs an action upon finishing a vertex in a graph. This method does nothing and is designed to be overridden in subclasses.

Parameters:

g - The graph.

u - The vertex just finished.