rust 63 lines · 9 steps

Detecting cycles with three-color DFS in Rust

A dependency graph finds cycles by coloring nodes white, gray, and black during a depth-first search.

Explained by highlit
Intermediate graph-algorithms cycle-detection depth-first-search recursion state-machine
1use std::collections::HashMap;
2 
3#[derive(Clone, Copy, PartialEq)]
4enum Color {
5 White,
6 Gray,
7 Black,
8}
9 
10pub struct DependencyGraph {
11 edges: HashMap<String, Vec<String>>,
12}
13 
14impl DependencyGraph {
15 pub fn new() -> Self {
16 Self { edges: HashMap::new() }
17 }
18 
19 pub fn add_dependency(&mut self, task: &str, depends_on: &str) {
20 self.edges.entry(task.to_string()).or_default().push(depends_on.to_string());
21 self.edges.entry(depends_on.to_string()).or_default();
22 }
23 
24 pub fn find_cycle(&self) -> Option<Vec<String>> {
25 let mut colors: HashMap<&str, Color> = self.edges.keys().map(|k| (k.as_str(), Color::White)).collect();
26 let mut stack = Vec::new();
27 
28 for node in self.edges.keys() {
29 if colors[node.as_str()] == Color::White {
30 if let Some(cycle) = self.visit(node, &mut colors, &mut stack) {
31 return Some(cycle);
32 }
33 }
34 }
35 None
36 }
37 
38 fn visit<'a>(&'a self, node: &'a str, colors: &mut HashMap<&'a str, Color>, stack: &mut Vec<&'a str>) -> Option<Vec<String>> {
39 colors.insert(node, Color::Gray);
40 stack.push(node);
41 
42 for next in &self.edges[node] {
43 match colors[next.as_str()] {
44 Color::Gray => {
45 let start = stack.iter().position(|n| *n == next.as_str()).unwrap();
46 let mut cycle: Vec<String> = stack[start..].iter().map(|s| s.to_string()).collect();
47 cycle.push(next.clone());
48 return Some(cycle);
49 }
50 Color::White => {
51 if let Some(cycle) = self.visit(next, colors, stack) {
52 return Some(cycle);
53 }
54 }
55 Color::Black => {}
56 }
57 }
58 
59 stack.pop();
60 colors.insert(node, Color::Black);
61 None
62 }
63}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Three-color marking distinguishes unvisited, in-progress, and fully-explored nodes, which is what makes cycle detection precise.
  2. 2Hitting a gray node during DFS means you've looped back onto the current recursion path — that's a cycle.
  3. 3Tracking the active path on a stack lets you reconstruct the exact cycle, not just report that one exists.

Related explainers

python 
class Parser:
    def __init__(self, text):
        self.tokens = self._tokenize(text)
        self.pos = 0

A recursive descent arithmetic parser

recursive-descent tokenizer operator-precedence
Intermediate 9 steps
rust 
use axum::{
    extract::{FromRef, FromRequestParts},
    http::{header, request::Parts, StatusCode},
    RequestPartsExt,

How a JWT extractor works in Axum

jwt authentication extractors
Intermediate 8 steps
java 
public final class CircuitBreaker {
 
    private enum State { CLOSED, OPEN, HALF_OPEN }
 

How a circuit breaker guards failing calls

state-machine resilience concurrency
Advanced 7 steps
rust 
#[derive(Deserialize)]
pub struct CreateArticle {
    title: String,
    body: String,

Building a create endpoint in Axum

extractors json-deserialization sqlx
Intermediate 7 steps
rust 
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, Ordering};
 
use axum::body::Body;

A maintenance-mode gate in Axum

middleware shared-state atomics
Intermediate 7 steps
rust 
use axum::body::Bytes;
use axum::http::{header, HeaderValue, StatusCode};
use axum::response::{IntoResponse, Response};
use serde::Serialize;

Custom Axum responses with per-user ETags

etag trait-implementation generics
Intermediate 7 steps

Share this explainer

Here's the card — post it anywhere.

Detecting cycles with three-color DFS in Rust — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code