```
pub fn depth_first_search<G, I, F, C>(graph: G, starts: I, visitor: F) -> Cwhere
G: IntoNeighbors + Visitable,
I: IntoIterator<Item = <G as GraphBase>::NodeId>,
F: FnMut(DfsEvent<<G as GraphBase>::NodeId>) -> C,
C: ControlFlow,
```

## Expand description

A recursive depth first search.

Starting points are the nodes in the iterator `starts`

(specify just one
start vertex *x* by using `Some(x)`

).

The traversal emits discovery and finish events for each reachable vertex,
and edge classification of each reachable edge. `visitor`

is called for each
event, see `DfsEvent`

for possible values.

The return value should implement the trait `ControlFlow`

, and can be used to change
the control flow of the search.

`Control`

Implements `ControlFlow`

such that `Control::Continue`

resumes the search.
`Control::Break`

will stop the visit early, returning the contained value.
`Control::Prune`

will stop traversing any additional edges from the current
node and proceed immediately to the `Finish`

event.

There are implementations of `ControlFlow`

for `()`

, and `Result<C, E>`

where
`C: ControlFlow`

. The implementation for `()`

will continue until finished.
For `Result`

, upon encountering an `E`

it will break, otherwise acting the same as `C`

.

***Panics** if you attempt to prune a node from its `Finish`

event.

## Example returning `Control`

.

Find a path from vertex 0 to 5, and exit the visit as soon as we reach the goal vertex.

```
use petgraph::prelude::*;
use petgraph::graph::node_index as n;
use petgraph::visit::depth_first_search;
use petgraph::visit::{DfsEvent, Control};
let gr: Graph<(), ()> = Graph::from_edges(&[
(0, 1), (0, 2), (0, 3),
(1, 3),
(2, 3), (2, 4),
(4, 0), (4, 5),
]);
// record each predecessor, mapping node → node
let mut predecessor = vec![NodeIndex::end(); gr.node_count()];
let start = n(0);
let goal = n(5);
depth_first_search(&gr, Some(start), |event| {
if let DfsEvent::TreeEdge(u, v) = event {
predecessor[v.index()] = u;
if v == goal {
return Control::Break(v);
}
}
Control::Continue
});
let mut next = goal;
let mut path = vec![next];
while next != start {
let pred = predecessor[next.index()];
path.push(pred);
next = pred;
}
path.reverse();
assert_eq!(&path, &[n(0), n(2), n(4), n(5)]);
```

## Example returning a `Result`

.

```
use petgraph::graph::node_index as n;
use petgraph::prelude::*;
use petgraph::visit::depth_first_search;
use petgraph::visit::{DfsEvent, Time};
let gr: Graph<(), ()> = Graph::from_edges(&[(0, 1), (1, 2), (1, 1), (2, 1)]);
let start = n(0);
let mut back_edges = 0;
let mut discover_time = 0;
// Stop the search, the first time a BackEdge is encountered.
let result = depth_first_search(&gr, Some(start), |event| {
match event {
// In the cases where Ok(()) is returned,
// Result falls back to the implementation of Control on the value ().
// In the case of (), this is to always return Control::Continue.
// continuing the search.
DfsEvent::Discover(_, Time(t)) => {
discover_time = t;
Ok(())
}
DfsEvent::BackEdge(_, _) => {
back_edges += 1;
// the implementation of ControlFlow for Result,
// treats this Err value as Continue::Break
Err(event)
}
_ => Ok(()),
}
});
// Even though the graph has more than one cycle,
// The number of back_edges visited by the search should always be 1.
assert_eq!(back_edges, 1);
println!("discover time:{:?}", discover_time);
println!("number of backedges encountered: {}", back_edges);
println!("back edge: {:?}", result);
```