edu.princeton.cs.algs4

Class DepthFirstSearch

java.lang.Object

edu.princeton.cs.algs4.DepthFirstSearch

public class DepthFirstSearch
extends java.lang.Object

The DepthFirstSearch class represents a data type for determining the vertices connected to a given source vertex s in an undirected graph. For versions that find the paths, see DepthFirstPaths and BreadthFirstPaths.

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. 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.

Constructor Summary

Constructors

Constructor and Description
DepthFirstSearch(Graph G, int s) Computes the vertices in graph G that are connected to the source vertex s.

Method Summary

Modifier and Type	Method and Description
int	count() Returns the number of vertices connected to the source vertex s.
static void	main(java.lang.String[] args) Unit tests the DepthFirstSearch data type.
boolean	marked(int v) Is there a path between the source vertex s and vertex v?

Methods inherited from class java.lang.Object

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

Constructor Detail

DepthFirstSearch

public DepthFirstSearch(Graph G,
                        int s)

Computes the vertices in graph G that are connected to the source vertex s.

Parameters:

G - the graph

s - the source vertex

Throws:

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

Method Detail

marked

public boolean marked(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

Throws:

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

count

public int count()

Returns the number of vertices connected to the source vertex s.

Returns:

the number of vertices connected to the source vertex s

main

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

Unit tests the DepthFirstSearch data type.

Parameters:

args - the command-line arguments