edu.princeton.cs.algorithms

Class DepthFirstDirectedPaths

java.lang.Object

edu.princeton.cs.algorithms.DepthFirstDirectedPaths

public class DepthFirstDirectedPaths
extends Object

The DepthFirstDirectedPaths class represents a data type for finding directed paths from a source vertex s to every other vertex in the digraph.

This implementation uses depth-first search. 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 graph) proportional to V.

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

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors

Constructor and Description
DepthFirstDirectedPaths(Digraph G, int s) Computes a directed path from s to every other vertex in digraph G.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	hasPathTo(int v) Is there a directed path from the source vertex s to vertex v?
static void	main(String[] args) Unit tests the DepthFirstDirectedPaths data type.
Iterable<Integer>	pathTo(int v) Returns a directed path from the source vertex s to vertex v, or null if no such path.

Methods inherited from class java.lang.Object

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

Constructor Detail

DepthFirstDirectedPaths

public DepthFirstDirectedPaths(Digraph G,
                       int s)

Computes a directed path from s to every other vertex in digraph G.

Parameters:

G - the digraph

s - the source vertex

Method Detail

hasPathTo

public boolean hasPathTo(int v)

Is there a directed path from the source vertex s to vertex v?

Parameters:

v - the vertex

Returns:

true if there is a directed path from the source vertex s to vertex v, false otherwise

pathTo

public Iterable<Integer> pathTo(int v)

Returns a directed path from the source vertex s to vertex v, or null if no such path.

Parameters:

v - the vertex

Returns:

the sequence of vertices on a directed path from the source vertex s to vertex v, as an Iterable

main

public static void main(String[] args)

Unit tests the DepthFirstDirectedPaths data type.