Class DirectedDFS

java.lang.Object

DirectedDFS

public class DirectedDFS
extends java.lang.Object

The DirectedDFS class represents a data type for determining the vertices reachable from a given source vertex s (or set of source vertices) in a digraph. For versions that find the paths, see DepthFirstDirectedPaths and BreadthFirstDirectedPaths.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges.

For additional documentation, see Section 4.1 of Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne.

Constructor Summary

Constructors

Constructor and Description
DirectedDFS(Digraph G, int s) Computes the vertices in digraph G that are reachable from the source vertex s.
DirectedDFS(Digraph G, java.lang.Iterable<java.lang.Integer> sources) Computes the vertices in digraph G that are connected to any of the source vertices sources.

Method Summary

Methods

Modifier and Type	Method and Description
int	count() Returns the number of vertices reachable from the source vertex (or source vertices).
static void	main(java.lang.String[] args) Unit tests the DirectedDFS data type.
boolean	marked(int v) Is there a directed path from the source vertex (or any of the source vertices) and vertex v?

Methods inherited from class java.lang.Object

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

Constructor Detail

DirectedDFS

public DirectedDFS(Digraph G,
           int s)

Computes the vertices in digraph G that are reachable from the source vertex s.

Parameters:

G - the digraph

s - the source vertex

DirectedDFS

public DirectedDFS(Digraph G,
           java.lang.Iterable<java.lang.Integer> sources)

Computes the vertices in digraph G that are connected to any of the source vertices sources.

Parameters:

G - the graph

sources - the source vertices

Method Detail

marked

public boolean marked(int v)

Is there a directed path from the source vertex (or any of the source vertices) and vertex v?

Parameters:

v - the vertex

Returns:

true if there is a directed path, false otherwise

count

public int count()

Returns the number of vertices reachable from the source vertex (or source vertices).

Returns:

the number of vertices reachable from the source vertex (or source vertices)

main

public static void main(java.lang.String[] args)

Unit tests the DirectedDFS data type.