Traversal Algorithms

Breadth-First Search (BFS)

Category: Traversal Time: O(V + E) Space: O(V)

BFS performs level-order traversal starting from a source node. It visits all nodes at depth 1 before depth 2, ensuring the shortest hop count to each reachable node.

Implementation

Queue-based with a VecDeque:

fn bfs(&self, start: usize) -> Vec<usize> {
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    let mut path = Vec::new();

    queue.push_back(start);
    visited.insert(start);

    while let Some(node) = queue.pop_front() {
        path.push(node);
        for &(neighbor, _) in self.adjacency.get(&node).unwrap_or(&vec![]) {
            if visited.insert(neighbor) {
                queue.push_back(neighbor);
            }
        }
    }
    path
}

When to Use

• Finding shortest paths in unweighted graphs (hop count)
• Level-by-level exploration
• Connected component detection

API Request

curl -X POST http://localhost:8000/process_file \
  -F "file=@graph.txt" \
  -F 'request={"algorithm":"bfs","file_format":"edge_list","start_node":0}'

Visualization

Animation reveals nodes in BFS visit order — you can watch the wavefront expand level by level. Nodes are colored cyan as they are visited.

---

Depth-First Search (DFS)

Category: Traversal Time: O(V + E) Space: O(V)

DFS explores as far as possible along each branch before backtracking. The implementation is iterative (using an explicit stack) rather than recursive — critical for stack safety on large graphs.

Implementation

Iterative stack-based DFS:

fn dfs(&self, start: usize) -> Vec<usize> {
    let mut visited = HashSet::new();
    let mut stack = vec![start];
    let mut path = Vec::new();

    while let Some(node) = stack.pop() {
        if visited.insert(node) {
            path.push(node);
            if let Some(neighbors) = self.adjacency.get(&node) {
                // Push in reverse so first neighbor is processed first
                for &(neighbor, _) in neighbors.iter().rev() {
                    if !visited.contains(&neighbor) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }
    path
}

Why iterative?

Recursive DFS causes stack overflows on graphs with paths longer than ~8,000 nodes (default Rust stack: ~8MB). The iterative implementation is safe for graphs of any size.

When to Use

• Cycle detection
• Topological ordering (use Topological Sort instead for guaranteed ordering)
• Pathfinding in maze-like structures
• Detecting connected components

API Request

curl -X POST http://localhost:8000/process_file \
  -F "file=@graph.txt" \
  -F 'request={"algorithm":"dfs","file_format":"edge_list","start_node":0}'

Visualization

DFS animation shows the characteristic deep-dive behavior — following one path to its end before backtracking. The contrast with BFS is visually clear on tree-structured or layered graphs.