edu.princeton.cs.algs4

Class NonrecursiveDirectedDFS

java.lang.Object

edu.princeton.cs.algs4.NonrecursiveDirectedDFS

public class NonrecursiveDirectedDFS
extends java.lang.Object

The NonrecursiveDirectedDFS class represents a data type for finding the vertices reachable from a source vertex s in the digraph.

This implementation uses a nonrecursive version of depth-first search with an explicit stack. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. It uses extra space (not including the digraph) proportional to V.

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

Constructor Summary

Constructors

Constructor and Description
NonrecursiveDirectedDFS(Digraph G, int s) Computes the vertices reachable from the source vertex s in the digraph G.

Method Summary

Modifier and Type	Method and Description
static void	main(java.lang.String[] args) Unit tests the NonrecursiveDirectedDFS data type.
boolean	marked(int v) Is vertex v reachable from the source vertex s?

Methods inherited from class java.lang.Object

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

Constructor Detail

NonrecursiveDirectedDFS

public NonrecursiveDirectedDFS(Digraph G,
                               int s)

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

Parameters:

G - the digraph

s - the source vertex

Throws:

java.lang.IllegalArgumentException - unless 0 <= s < V

Method Detail

marked

public boolean marked(int v)

Is vertex v reachable from the source vertex s?

Parameters:

v - the vertex

Returns:

true if vertex v is reachable from the source vertex s, and false otherwise

Throws:

java.lang.IllegalArgumentException - unless 0 <= v < V

main

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

Unit tests the NonrecursiveDirectedDFS data type.

Parameters:

args - the command-line arguments