Package edu.princeton.cs.algs4

Class DirectedDFS

Object

edu.princeton.cs.algs4.DirectedDFS

public class DirectedDFS
extends 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. Each instance method takes Θ(1) time. It uses Θ(V) extra space (not including the digraph).

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

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
int	count()	Returns the number of vertices reachable from the source vertex (or source vertices).
static void	main(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, 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

Throws:

IllegalArgumentException - unless 0 <= s < V

DirectedDFS

public DirectedDFS(Digraph G,
                   Iterable<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

Throws:

IllegalArgumentException - if sources is null

IllegalArgumentException - if sources contains no vertices

IllegalArgumentException - unless 0 <= s < V for each vertex s in sources

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

Throws:

IllegalArgumentException - unless 0 <= v < V

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(String[] args)

Unit tests the DirectedDFS data type.

Parameters:

args - the command-line arguments