edu.princeton.cs.algs4

## Class DepthFirstSearch

• Object
• edu.princeton.cs.algs4.DepthFirstSearch

• ```public class DepthFirstSearch
extends 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.

Author:
Robert Sedgewick, 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

Methods
Modifier and Type Method and Description
`int` `count()`
Returns the number of vertices connected to the source vertex `s`.
`static void` `main(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 Object

`clone, equals, finalize, 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:
`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:
`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(String[] args)`
Unit tests the `DepthFirstSearch` data type.
Parameters:
`args` - the command-line arguments