254 Intermediate

Graph DFS

Graphs

Tutorial Video

Text description (accessibility)

This video demonstrates the "Graph DFS" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Graphs. Perform a depth-first search (DFS) on a directed graph represented as an adjacency list, returning the nodes in pre-order visit sequence with no duplicates — even when multiple paths lead to the same node. Key difference from OCaml: 1. **Visited set:** OCaml uses an immutable `Set.Make(String)` threaded through returns; Rust uses a mutable `HashSet<&str>` passed by `&mut` reference.

Tutorial

The Problem

Perform a depth-first search (DFS) on a directed graph represented as an adjacency list, returning the nodes in pre-order visit sequence with no duplicates — even when multiple paths lead to the same node.

🎯 Learning Outcomes

• How Rust's HashSet replaces OCaml's purely functional Set.Make module

• Iterative DFS with an explicit stack vs. recursive DFS that mirrors OCaml's structure

• Lifetime annotations on graph references: &'a HashMap<&str, Vec<&str>>

• Why HashSet::insert returning bool eliminates an extra contains check

🦀 The Rust Way

The idiomatic Rust solution uses an iterative stack-based DFS with a HashSet for O(1) visited lookup. Neighbors are pushed in reverse order so the first neighbor is processed first, matching OCaml's left-to-right traversal. The functional variant uses a recursive inner function with &mut HashSet — mutation is contained, the interface stays pure, and it directly parallels the OCaml go helper.

Code Example

pub fn dfs<'a>(graph: &'a HashMap<&str, Vec<&str>>, start: &'a str) -> Vec<&'a str> {
    let mut visited: HashSet<&str> = HashSet::new();
    let mut stack: Vec<&str> = vec![start];
    let mut result: Vec<&str> = Vec::new();

    while let Some(node) = stack.pop() {
        if !visited.insert(node) {
            continue;
        }
        result.push(node);
        if let Some(neighbors) = graph.get(node) {
            for &neighbor in neighbors.iter().rev() {
                if !visited.contains(neighbor) {
                    stack.push(neighbor);
                }
            }
        }
    }
    result
}

module SS = Set.Make(String)

let dfs graph start =
  let rec go visited node =
    if SS.mem node visited then (visited, [])
    else
      let visited = SS.add node visited in
      let neighbors = try List.assoc node graph with Not_found -> [] in
      let visited, paths = List.fold_left (fun (vis, acc) n ->
        let vis, path = go vis n in
        (vis, acc @ path)
      ) (visited, []) neighbors in
      (visited, node :: paths)
  in
  snd (go SS.empty start)

Key Differences

Visited set: OCaml uses an immutable Set.Make(String) threaded through returns; Rust uses a mutable HashSet<&str> passed by &mut reference.

Recursion vs. iteration: OCaml's natural expression is recursive; Rust prefers an iterative stack to avoid stack-overflow on deep graphs.

Graph representation: OCaml uses association lists ((string * string list) list) mirroring List.assoc; Rust uses HashMap<&str, Vec<&str>> for O(1) neighbor lookup.

Insert semantics: HashSet::insert returns false when already present, letting us skip the contains + insert double-check OCaml needs with SS.mem + SS.add.

OCaml Approach

OCaml threads the visited set as a pure value through recursion — go returns (new_visited, path) and the caller receives the updated set, never mutating in place. List.fold_left chains neighbor visits, accumulating both the growing visited set and the partial path. The result is the clean separation of state passing that characterises pure functional code.

Full Source

#![allow(clippy::all)]
use std::collections::{HashMap, HashSet};

/// Idiomatic Rust DFS: iterative with an explicit stack and HashSet for visited tracking.
/// Returns nodes in DFS pre-order — the same traversal order as the OCaml recursive version.
///
/// Takes `&HashMap<&str, Vec<&str>>` — borrows the graph, no allocation of keys needed.
pub fn dfs<'a>(graph: &'a HashMap<&str, Vec<&str>>, start: &'a str) -> Vec<&'a str> {
    let mut visited: HashSet<&str> = HashSet::new();
    // Stack-based DFS: push neighbors in reverse so left-to-right order is preserved
    let mut stack: Vec<&str> = vec![start];
    let mut result: Vec<&str> = Vec::new();

    while let Some(node) = stack.pop() {
        if !visited.insert(node) {
            // insert returns false when node was already present
            continue;
        }
        result.push(node);
        if let Some(neighbors) = graph.get(node) {
            // Reverse so the first neighbor ends up on top of the stack
            for &neighbor in neighbors.iter().rev() {
                if !visited.contains(neighbor) {
                    stack.push(neighbor);
                }
            }
        }
    }

    result
}

/// Functional-style DFS using an assoc-list graph (mirrors OCaml's `List.assoc`).
/// Recursive inner function threads the visited set, paralleling the OCaml structure.
///
/// OCaml threads `visited` as a pure value through returns; here we use `&mut HashSet`
/// for the same logical effect without repeated allocation.
pub fn dfs_recursive<'a>(graph: &[(&'a str, Vec<&'a str>)], start: &'a str) -> Vec<&'a str> {
    fn go<'a>(
        graph: &[(&'a str, Vec<&'a str>)],
        visited: &mut HashSet<&'a str>,
        node: &'a str,
    ) -> Vec<&'a str> {
        if !visited.insert(node) {
            return vec![];
        }
        // Mirror OCaml's `List.assoc node graph`
        let neighbors = graph
            .iter()
            .find(|(n, _)| *n == node)
            .map(|(_, ns)| ns.as_slice())
            .unwrap_or(&[]);

        // node :: paths  (pre-order: emit node before recursing into neighbors)
        let mut path = vec![node];
        for &neighbor in neighbors {
            path.extend(go(graph, visited, neighbor));
        }
        path
    }

    let mut visited = HashSet::new();
    go(graph, &mut visited, start)
}

#[cfg(test)]
mod tests {
    use super::*;

    fn diamond_hashmap() -> HashMap<&'static str, Vec<&'static str>> {
        let mut g = HashMap::new();
        g.insert("a", vec!["b", "c"]);
        g.insert("b", vec!["d"]);
        g.insert("c", vec!["d"]);
        g.insert("d", vec![]);
        g
    }

    fn diamond_assoc() -> Vec<(&'static str, Vec<&'static str>)> {
        vec![
            ("a", vec!["b", "c"]),
            ("b", vec!["d"]),
            ("c", vec!["d"]),
            ("d", vec![]),
        ]
    }

    // --- dfs (HashMap / iterative) ---

    #[test]
    fn test_dfs_visits_all_nodes() {
        let graph = diamond_hashmap();
        let order = dfs(&graph, "a");
        assert_eq!(order.len(), 4);
        let mut sorted = order.clone();
        sorted.sort_unstable();
        assert_eq!(sorted, vec!["a", "b", "c", "d"]);
    }

    #[test]
    fn test_dfs_start_is_first() {
        let graph = diamond_hashmap();
        let order = dfs(&graph, "a");
        assert_eq!(order[0], "a");
    }

    #[test]
    fn test_dfs_no_duplicate_visits() {
        // Diamond: d is reachable via a→b→d and a→c→d — must appear exactly once
        let graph = diamond_hashmap();
        let order = dfs(&graph, "a");
        let d_count = order.iter().filter(|&&n| n == "d").count();
        assert_eq!(d_count, 1);
    }

    #[test]
    fn test_dfs_single_node() {
        let mut graph = HashMap::new();
        graph.insert("x", vec![]);
        let order = dfs(&graph, "x");
        assert_eq!(order, vec!["x"]);
    }

    #[test]
    fn test_dfs_linear_chain() {
        let mut graph = HashMap::new();
        graph.insert("1", vec!["2"]);
        graph.insert("2", vec!["3"]);
        graph.insert("3", vec![]);
        let order = dfs(&graph, "1");
        assert_eq!(order, vec!["1", "2", "3"]);
    }

    #[test]
    fn test_dfs_pre_order() {
        // For the diamond graph with neighbors visited left-to-right,
        // DFS must reach "b" before "c" (b is the first neighbor of a)
        let graph = diamond_hashmap();
        let order = dfs(&graph, "a");
        let pos: HashMap<&str, usize> = order.iter().enumerate().map(|(i, &n)| (n, i)).collect();
        assert!(pos["a"] < pos["b"]);
        assert!(pos["b"] < pos["c"], "b must be explored before c in DFS");
        assert!(pos["b"] < pos["d"]);
    }

    // --- dfs_recursive (assoc-list / functional) ---

    #[test]
    fn test_recursive_visits_all_nodes() {
        let graph = diamond_assoc();
        let order = dfs_recursive(&graph, "a");
        assert_eq!(order.len(), 4);
        let mut sorted = order.clone();
        sorted.sort_unstable();
        assert_eq!(sorted, vec!["a", "b", "c", "d"]);
    }

    #[test]
    fn test_recursive_no_duplicate_visits() {
        let graph = diamond_assoc();
        let order = dfs_recursive(&graph, "a");
        let d_count = order.iter().filter(|&&n| n == "d").count();
        assert_eq!(d_count, 1);
    }

    #[test]
    fn test_recursive_matches_ocaml_order() {
        // OCaml output for the diamond graph is: a b d c
        let graph = diamond_assoc();
        let order = dfs_recursive(&graph, "a");
        assert_eq!(order, vec!["a", "b", "d", "c"]);
    }

    #[test]
    fn test_recursive_unknown_start_not_in_graph() {
        // Node with no entry in the assoc-list has no neighbors — treated as a leaf
        let graph = diamond_assoc();
        let order = dfs_recursive(&graph, "z");
        assert_eq!(order, vec!["z"]);
    }
}

(* OCaml Depth-First Search using a pure functional visited set *)

module SS = Set.Make(String)

(* Idiomatic OCaml DFS — visited set threaded as a pure value through recursion *)
let dfs graph start =
  let rec go visited node =
    if SS.mem node visited then (visited, [])
    else
      let visited = SS.add node visited in
      let neighbors = try List.assoc node graph with Not_found -> [] in
      let visited, paths = List.fold_left (fun (vis, acc) n ->
        let vis, path = go vis n in
        (vis, acc @ path)
      ) (visited, []) neighbors in
      (visited, node :: paths)
  in
  snd (go SS.empty start)

(* Recursive DFS returning only the path — slightly more direct *)
let dfs_simple graph start =
  let rec go visited node =
    if SS.mem node visited then (visited, [])
    else
      let visited' = SS.add node visited in
      let neighbors = try List.assoc node graph with Not_found -> [] in
      let visited'', rest = List.fold_left (fun (v, acc) n ->
        let v', p = go v n in (v', acc @ p)
      ) (visited', []) neighbors in
      (visited'', node :: rest)
  in
  snd (go SS.empty start)

let () =
  let g = [("a", ["b"; "c"]); ("b", ["d"]); ("c", ["d"]); ("d", [])] in

  let result = dfs g "a" in
  assert (result = ["a"; "b"; "d"; "c"]);

  let result2 = dfs_simple g "a" in
  assert (result2 = ["a"; "b"; "d"; "c"]);

  (* Single node *)
  let single = [("x", [])] in
  assert (dfs single "x" = ["x"]);

  (* Linear chain *)
  let chain = [("1", ["2"]); ("2", ["3"]); ("3", [])] in
  assert (dfs chain "1" = ["1"; "2"; "3"]);

  print_endline "ok"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    fn diamond_hashmap() -> HashMap<&'static str, Vec<&'static str>> {
        let mut g = HashMap::new();
        g.insert("a", vec!["b", "c"]);
        g.insert("b", vec!["d"]);
        g.insert("c", vec!["d"]);
        g.insert("d", vec![]);
        g
    }

    fn diamond_assoc() -> Vec<(&'static str, Vec<&'static str>)> {
        vec![
            ("a", vec!["b", "c"]),
            ("b", vec!["d"]),
            ("c", vec!["d"]),
            ("d", vec![]),
        ]
    }

    // --- dfs (HashMap / iterative) ---

    #[test]
    fn test_dfs_visits_all_nodes() {
        let graph = diamond_hashmap();
        let order = dfs(&graph, "a");
        assert_eq!(order.len(), 4);
        let mut sorted = order.clone();
        sorted.sort_unstable();
        assert_eq!(sorted, vec!["a", "b", "c", "d"]);
    }

    #[test]
    fn test_dfs_start_is_first() {
        let graph = diamond_hashmap();
        let order = dfs(&graph, "a");
        assert_eq!(order[0], "a");
    }

    #[test]
    fn test_dfs_no_duplicate_visits() {
        // Diamond: d is reachable via a→b→d and a→c→d — must appear exactly once
        let graph = diamond_hashmap();
        let order = dfs(&graph, "a");
        let d_count = order.iter().filter(|&&n| n == "d").count();
        assert_eq!(d_count, 1);
    }

    #[test]
    fn test_dfs_single_node() {
        let mut graph = HashMap::new();
        graph.insert("x", vec![]);
        let order = dfs(&graph, "x");
        assert_eq!(order, vec!["x"]);
    }

    #[test]
    fn test_dfs_linear_chain() {
        let mut graph = HashMap::new();
        graph.insert("1", vec!["2"]);
        graph.insert("2", vec!["3"]);
        graph.insert("3", vec![]);
        let order = dfs(&graph, "1");
        assert_eq!(order, vec!["1", "2", "3"]);
    }

    #[test]
    fn test_dfs_pre_order() {
        // For the diamond graph with neighbors visited left-to-right,
        // DFS must reach "b" before "c" (b is the first neighbor of a)
        let graph = diamond_hashmap();
        let order = dfs(&graph, "a");
        let pos: HashMap<&str, usize> = order.iter().enumerate().map(|(i, &n)| (n, i)).collect();
        assert!(pos["a"] < pos["b"]);
        assert!(pos["b"] < pos["c"], "b must be explored before c in DFS");
        assert!(pos["b"] < pos["d"]);
    }

    // --- dfs_recursive (assoc-list / functional) ---

    #[test]
    fn test_recursive_visits_all_nodes() {
        let graph = diamond_assoc();
        let order = dfs_recursive(&graph, "a");
        assert_eq!(order.len(), 4);
        let mut sorted = order.clone();
        sorted.sort_unstable();
        assert_eq!(sorted, vec!["a", "b", "c", "d"]);
    }

    #[test]
    fn test_recursive_no_duplicate_visits() {
        let graph = diamond_assoc();
        let order = dfs_recursive(&graph, "a");
        let d_count = order.iter().filter(|&&n| n == "d").count();
        assert_eq!(d_count, 1);
    }

    #[test]
    fn test_recursive_matches_ocaml_order() {
        // OCaml output for the diamond graph is: a b d c
        let graph = diamond_assoc();
        let order = dfs_recursive(&graph, "a");
        assert_eq!(order, vec!["a", "b", "d", "c"]);
    }

    #[test]
    fn test_recursive_unknown_start_not_in_graph() {
        // Node with no entry in the assoc-list has no neighbors — treated as a leaf
        let graph = diamond_assoc();
        let order = dfs_recursive(&graph, "z");
        assert_eq!(order, vec!["z"]);
    }
}

Deep Comparison

OCaml vs Rust: Graph DFS

Side-by-Side Code

OCaml

module SS = Set.Make(String)

let dfs graph start =
  let rec go visited node =
    if SS.mem node visited then (visited, [])
    else
      let visited = SS.add node visited in
      let neighbors = try List.assoc node graph with Not_found -> [] in
      let visited, paths = List.fold_left (fun (vis, acc) n ->
        let vis, path = go vis n in
        (vis, acc @ path)
      ) (visited, []) neighbors in
      (visited, node :: paths)
  in
  snd (go SS.empty start)

Rust (idiomatic — iterative stack)

pub fn dfs<'a>(graph: &'a HashMap<&str, Vec<&str>>, start: &'a str) -> Vec<&'a str> {
    let mut visited: HashSet<&str> = HashSet::new();
    let mut stack: Vec<&str> = vec![start];
    let mut result: Vec<&str> = Vec::new();

    while let Some(node) = stack.pop() {
        if !visited.insert(node) {
            continue;
        }
        result.push(node);
        if let Some(neighbors) = graph.get(node) {
            for &neighbor in neighbors.iter().rev() {
                if !visited.contains(neighbor) {
                    stack.push(neighbor);
                }
            }
        }
    }
    result
}

Rust (functional/recursive — mirrors OCaml)

pub fn dfs_recursive<'a>(graph: &[(&'a str, Vec<&'a str>)], start: &'a str) -> Vec<&'a str> {
    fn go<'a>(
        graph: &[(&'a str, Vec<&'a str>)],
        visited: &mut HashSet<&'a str>,
        node: &'a str,
    ) -> Vec<&'a str> {
        if !visited.insert(node) {
            return vec![];
        }
        let neighbors = graph
            .iter()
            .find(|(n, _)| *n == node)
            .map(|(_, ns)| ns.as_slice())
            .unwrap_or(&[]);

        let mut path = vec![node];
        for &neighbor in neighbors {
            path.extend(go(graph, visited, neighbor));
        }
        path
    }
    let mut visited = HashSet::new();
    go(graph, &mut visited, start)
}

Type Signatures

Concept	OCaml	Rust
DFS function	`val dfs : (string * string list) list -> string -> string list`	`fn dfs<'a>(graph: &'a HashMap<&str, Vec<&str>>, start: &'a str) -> Vec<&'a str>`
Graph type	`(string * string list) list`	`HashMap<&str, Vec<&str>>`
Visited set	`SS.t` (balanced BST, O(log n))	`HashSet<&str>` (hash table, O(1))
Node type	`string` (owned, GC-managed)	`&str` (borrowed, lifetime-tracked)
Neighbor lookup	`List.assoc node graph` (O(n))	`graph.get(node)` (O(1))

Key Insights

Pure vs. mutable state: OCaml threads visited as an immutable value through every return — go returns (new_visited, path). Rust uses &mut HashSet to achieve the same result with a single allocation and no copying. The observable behaviour is identical; only the mechanism differs.

**insert as a membership test:** HashSet::insert returns bool — false means already present. This lets Rust combine "is visited?" and "mark visited" into one atomic call, eliminating the OCaml pattern of SS.mem followed by SS.add.

Stack vs. recursion: OCaml's natural style is deep recursion with tail-call optimisation available when the compiler detects it. Rust prefers an explicit stack for DFS because Rust does not guarantee TCO, and deep recursion risks a stack overflow on large graphs.

Graph representation trade-off: OCaml's association list ((string * string list) list) is idiomatic for small graphs and mirrors the lambda-calculus tradition. Rust's HashMap gives O(1) lookups; the assoc-list variant (&[(&str, Vec<&str>)]) is provided for a direct structural parallel to the OCaml code.

Lifetime annotations: The 'a lifetime ties the output Vec<&'a str> to the graph's borrowed string data — the compiler proves at compile time that returned node references never outlive the graph. OCaml's GC makes this invisible; Rust makes it explicit.

When to Use Each Style

Use idiomatic Rust (iterative stack) when: your graph can be large or deep — iterative DFS will not overflow the call stack and avoids the overhead of allocating intermediate Vecs for every recursive call.

Use recursive Rust (functional style) when: you are translating OCaml or Haskell DFS code directly and want to preserve the structural correspondence for review or teaching, and the graph depth is bounded.

Exercises

Implement iterative DFS using an explicit Vec-based stack instead of recursion, ensuring the traversal order matches the recursive version.

Use DFS to detect cycles in a directed graph by tracking the current recursion path (gray nodes) and back edges.

Implement Tarjan's strongly connected components algorithm using DFS with a low-link array and a stack, returning each SCC as a Vec<NodeId>.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust