Depth-First Search, often called DFS, is one of the most important graph-traversal algorithms in computer science. It follows a simple but powerful idea: start from a node, explore one direction as far as possible, and only then backtrack to explore other paths. Because it travels deep before moving sideways, DFS becomes useful when you need to discover connections, understand structure, or search through complex relationships.
with hands-on learning.
get the skills and confidence to land your next move.
This algorithm is used in many real applications, including exploring file systems, solving mazes, performing topological sorting, detecting cycles, searching networks, and much more. In Rust, implementing DFS is an excellent way for beginners to learn recursion, stacks, ownership, and the beauty of safe memory handling. Rust gives us both speed and security, making DFS feel smooth and reliable even when the data grows large.
Program 1: Recursive DFS on an Adjacency List
This first program shows the classic recursive DFS approach using a simple adjacency list to represent the graph. It begins at a starting node and dives deeper until it cannot go further, making it a great introduction to the idea of depth-first exploration.
use std::collections::HashSet;
fn dfs_recursive(node: usize, graph: &Vec<Vec<usize>>, visited: &mut HashSet<usize>) {
if visited.contains(&node) {
return;
}
println!("Visited: {}", node);
visited.insert(node);
for &next in &graph[node] {
dfs_recursive(next, graph, visited);
}
}
fn main() {
let graph = vec![
vec![1, 2],
vec![0, 3],
vec![0, 4],
vec![1],
vec![2],
];
let mut visited = HashSet::new();
dfs_recursive(0, &graph, &mut visited);
}This program works by calling itself again and again whenever it finds a connected neighbor that has not been visited yet. The visited set helps prevent infinite loops, especially in graphs with cycles. Beginners can understand this approach easily because it follows the natural idea of “go deeper before returning.”
Program 2: Iterative DFS Using a Stack
Sometimes recursion may not be ideal, especially with deep graphs. This version uses a manual stack, making the process more explicit and giving beginners a chance to see how DFS really behaves behind the scenes.
use std::collections::HashSet;
fn dfs_iterative(start: usize, graph: &Vec<Vec<usize>>) {
let mut visited = HashSet::new();
let mut stack = vec![start];
while let Some(node) = stack.pop() {
if !visited.contains(&node) {
println!("Visited: {}", node);
visited.insert(node);
for &next in &graph[node] {
stack.push(next);
}
}
}
}
fn main() {
let graph = vec![
vec![1, 2],
vec![0, 3],
vec![0, 4],
vec![1],
vec![2],
];
dfs_iterative(0, &graph);
}This code moves through the graph with full control over the traversal order. Because everything is handled by the stack, beginners can see more clearly how DFS pushes deeper paths onto the stack before exploring others. It also helps avoid recursion limits in very large structures.
Program 3: DFS on a Weighted Graph
In some situations, graphs carry weights on edges. DFS does not use these weights to make decisions but can still traverse the structure and inspect the weights as it goes.
use std::collections::HashSet;
fn dfs_weighted(node: usize, graph: &Vec<Vec<(usize, i32)>>, visited: &mut HashSet<usize>) {
if visited.contains(&node) {
return;
}
println!("At node: {}", node);
visited.insert(node);
for &(next, weight) in &graph[node] {
println!("Edge to {} has weight {}", next, weight);
dfs_weighted(next, graph, visited);
}
}
fn main() {
let graph = vec![
vec![(1, 5), (2, 3)],
vec![(0, 5), (3, 2)],
vec![(0, 3), (4, 7)],
vec![(1, 2)],
vec![(2, 7)],
];
let mut visited = HashSet::new();
dfs_weighted(0, &graph, &mut visited);
}This version shows how DFS can adapt to more advanced graph structures. The program still moves deeply, but now displays additional information along the way. Beginners get used to handling more complex data without changing the core DFS logic.
Program 4: DFS to Detect Connected Components
Graphs sometimes have separate groups of nodes that are not connected to each other. DFS can help identify these groups, known as connected components.
use std::collections::HashSet;
fn explore(node: usize, graph: &Vec<Vec<usize>>, visited: &mut HashSet<usize>) {
if visited.contains(&node) {
return;
}
visited.insert(node);
for &next in &graph[node] {
explore(next, graph, visited);
}
}
fn main() {
let graph = vec![
vec![1],
vec![0, 2],
vec![1],
vec![4],
vec![3],
];
let mut visited = HashSet::new();
let mut count = 0;
for i in 0..graph.len() {
if !visited.contains(&i) {
count += 1;
println!("Starting component {}", count);
explore(i, &graph, &mut visited);
}
}
println!("Total connected components: {}", count);
}This program shows DFS working across separate zones of a graph. Each time DFS starts from a fresh unvisited node, a new component is counted. Beginners see how DFS gives insight into the structure of a graph and helps understand how groups of nodes relate.
Program 5: DFS Pathfinding Between Two Nodes
DFS can also be used to find a path between one node and another. This program tries to reach a target node and records the path during its exploration.
use std::collections::HashSet;
fn find_path(
node: usize,
target: usize,
graph: &Vec<Vec<usize>>,
visited: &mut HashSet<usize>,
path: &mut Vec<usize>,
) -> bool {
visited.insert(node);
path.push(node);
if node == target {
return true;
}
for &next in &graph[node] {
if !visited.contains(&next) {
if find_path(next, target, graph, visited, path) {
return true;
}
}
}
path.pop();
false
}
fn main() {
let graph = vec![
vec![1, 2],
vec![0, 3],
vec![0],
vec![1, 4],
vec![3],
];
let mut visited = HashSet::new();
let mut path = Vec::new();
if find_path(0, 4, &graph, &mut visited, &mut path) {
println!("Path to target: {:?}", path);
} else {
println!("No path found");
}
}This example highlights how DFS naturally fits with backtracking. Each time DFS tries a direction and discovers it does not lead to the target, it steps back and tries another move. Beginners can clearly see how recursion allows the algorithm to “remember” the path and adjust it as it searches.
Frequently Asked Questions (FAQ)
This section helps clear up common questions beginners often ask about Depth-First Search in Rust. The goal is to make the ideas easy to understand, especially if you are still getting comfortable with graph algorithms.
Q1: What is the time complexity of DFS?
The time complexity of DFS is usually linear, meaning it depends on how many nodes and edges the graph has. In simple terms, DFS goes through every corner of the structure, so it takes O(V + E), where V is the number of nodes and E is the number of edges. This makes it efficient for most graph problems.
Q2: Does DFS always find the shortest path?
DFS does not focus on finding the shortest route. It goes deep into one direction first, which means it may skip a shorter path somewhere else. If you want the shortest path, methods like Breadth-First Search are better choices for unweighted graphs.
Q3: Can DFS be used on trees and graphs?
DFS works very well on both trees and general graphs. In trees, it moves from the root downward in a natural way. In graphs, it explores every reachable part as long as you keep track of what has been visited to avoid going in circles.
Q4: Why do we need a visited set?
A visited set keeps DFS from repeating the same place again and again, especially in graphs with loops. Without this small safety step, DFS could get stuck following the same path forever. It also makes the algorithm faster and cleaner.
Q5: Is recursive DFS faster than iterative DFS?
Both recursive and iterative DFS give the same results and run in similar time. The main difference is in style and memory use. Recursion feels more natural for some people, while the iterative version avoids deep call stacks. The choice usually depends on the size of the graph and personal preference.
Conclusion
Depth-First Search is one of those algorithms that feels simple but opens the door to many deeper ideas in computer science. Learning how to write DFS in Rust teaches you more than just traversal; it shows you how recursion works, how stacks behave, and how safe memory handling leads to clearer programs. Whether you work with graphs, networks, puzzles, or data structures, DFS gives you a dependable tool to explore and understand complex information. With practice and curiosity, you will become more confident in both Rust and algorithmic thinking, putting you on a strong path toward solving larger and more interesting problems.
