Depth-First Search
Depth-First Search (DFS) on a graph.
DFS explores as deep as possible along each branch before backtracking. It is the natural building block for topological order, cycle detection on directed/undirected graphs, strongly connected components, and tree traversals.
The Rust crate lives at dfs/src/lib.rs; build & run it with:
$ cd dfs && cargo run
$ cd dfs && cargo test
Generated API reference for the Depth-First Search crate. View the rendered API reference →
1//! Depth-First Search (DFS) on a graph.
2//!
3//! DFS explores as deep as possible along each branch before
4//! backtracking. It is the natural building block for topological
5//! order, cycle detection on directed/undirected graphs, strongly
6//! connected components, and tree traversals.
7//!
8//! This module exposes DFS as two helpers operating on an adjacency
9//! list:
10//!
11//! * [`dfs_order`] — returns vertices in the order they are first
12//! visited (iterative, stack-based; safe for deep graphs).
13//! * [`has_cycle_undirected`] — detects whether an undirected graph
14//! contains a cycle.
15
16use std::collections::HashSet;
17
18/// Return the DFS visitation order starting from `source`.
19///
20/// Iterative implementation using an explicit stack, so it is safe for
21/// graphs deeper than the default Rust stack limit.
22///
23/// # Panics
24///
25/// Panics if `source >= graph.len()`.
26pub fn dfs_order(graph: &[Vec<usize>], source: usize) -> Vec<usize> {
27 assert!(source < graph.len(), "source vertex out of range");
28 let mut visited = vec![false; graph.len()];
29 let mut order = Vec::with_capacity(graph.len());
30 let mut stack: Vec<usize> = Vec::new();
31 stack.push(source);
32 while let Some(v) = stack.pop() {
33 if visited[v] {
34 continue;
35 }
36 visited[v] = true;
37 order.push(v);
38 // push neighbours in reverse so the natural left-to-right order
39 // is preserved in the resulting traversal
40 for &u in graph[v].iter().rev() {
41 if !visited[u] {
42 stack.push(u);
43 }
44 }
45 }
46 order
47}
48
49/// Detect whether an undirected graph contains a cycle.
50///
51/// Pass the adjacency list and edges must already be reciprocal (i.e.,
52/// for any edge `u -- v` you must include both `v` in `graph[u]` and
53/// `u` in `graph[v]`).
54pub fn has_cycle_undirected(graph: &[Vec<usize>]) -> bool {
55 let mut visited: HashSet<usize> = HashSet::new();
56 for start in 0..graph.len() {
57 if visited.contains(&start) {
58 continue;
59 }
60 // iterative DFS on the connected component of `start`
61 let mut stack: Vec<(usize, usize)> = Vec::new(); // (node, parent)
62 stack.push((start, usize::MAX));
63 while let Some((v, parent)) = stack.pop() {
64 if visited.contains(&v) {
65 // reached an already-visited node via a different path:
66 // this is a back edge, hence a cycle
67 return true;
68 }
69 visited.insert(v);
70 for &u in &graph[v] {
71 if u == parent {
72 continue;
73 }
74 stack.push((u, v));
75 }
76 }
77 }
78 false
79}