edu.princeton.cs.algorithms

Class DepthFirstPaths

java.lang.Object

edu.princeton.cs.algorithms.DepthFirstPaths

public class DepthFirstPaths
extends Object

The DepthFirstPaths class represents a data type for finding paths from a source vertex s to every other vertex in an undirected graph.

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
DepthFirstPaths(Graph G, int s) Computes a path between s and every other vertex in graph G.

Method Summary

Modifier and Type	Method and Description
boolean	hasPathTo(int v) Is there a path between the source vertex s and vertex v?
static void	main(String[] args) Unit tests the DepthFirstPaths data type.
Iterable<Integer>	pathTo(int v) Returns a path between the source vertex s and 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

DepthFirstPaths

public DepthFirstPaths(Graph G,
                       int s)

Computes a path between s and every other vertex in graph G.

Parameters:

G - the graph

s - the source vertex

Method Detail

hasPathTo

public boolean hasPathTo(int v)

Is there a path between the source vertex s and vertex v?

Parameters:

v - the vertex

Returns:

true if there is a path, false otherwise

pathTo

public Iterable<Integer> pathTo(int v)

Returns a path between the source vertex s and vertex v, or null if no such path.

Parameters:

v - the vertex

Returns:

the sequence of vertices on a path between the source vertex s and vertex v, as an Iterable

main

public static void main(String[] args)

Unit tests the DepthFirstPaths data type.