Depth-First Search (Recursive)

Visit a start vertex, then recurse into its first unvisited neighbour all the way down before backtracking. A visited set prevents revisiting, and neighbour insertion order fixes the visit sequence.

Algorithm

On the canonical 6-vertex graph from graph-adjacency-list, starting at vertex 1, the deterministic visit order is [1, 2, 4, 3, 5, 6]. Calls unwind 6 -> 5 -> 4 -> 3 -> 2 -> 1 after all vertices are visited.

Basic Implementation

basic.rs

use std::collections::HashMap;
fn dfs(v: i32, adj: &HashMap<i32, Vec<i32>>, visited: &mut HashMap<i32, bool>, order: &mut Vec<i32>) {
	visited.insert(v, true);
	order.push(v);
	for &nb in &adj[&v] {
		if !visited.contains_key(&nb) {
			dfs(nb, adj, visited, order);
		}
	}
}
fn main() {
	let mut adj: HashMap<i32, Vec<i32>> = HashMap::new();
	adj.insert(1, vec![2, 3]);
	adj.insert(2, vec![1, 4]);
	adj.insert(3, vec![1, 4]);
	adj.insert(4, vec![2, 3, 5]);
	adj.insert(5, vec![4, 6]);
	adj.insert(6, vec![5]);
	let mut visited: HashMap<i32, bool> = HashMap::new();
	let mut order: Vec<i32> = Vec::new();
	dfs(1, &adj, &mut visited, &mut order);
	println!("{:?}", order);
}

Complexity

Time: O(V + E)
Space: O(V) recursion depth

Implementation notes

Rust: a recursive dfs takes &HashMap plus &mut visited/order; {:?} prints the vector comma-separated.
The replay shows the current vertex, the visited set, and the running visit order after each entry, matching the lesson spec.

recursive descent Follow one branch to its end, then unwind and try the next neighbour.