Graph Traversal Visualization (BFS & DFS)

Interactive Traversal

Visualize Breadth-First Search (BFS) and Depth-First Search (DFS) on a sample graph.

Start Node: Traversal Type:

Speed: 600ms

Select a start node and traversal type, then click 'Start Traversal'.

Traversal Order

Queue / Stack

Graph Traversal Explained

Graph traversal algorithms systematically visit every node in a graph exactly once. The two most common methods are Breadth-First Search (BFS) and Depth-First Search (DFS).

Breadth-First Search (BFS):
- Explores the graph level by level. It starts at a source node, visits all its direct neighbors, then visits all neighbors of those neighbors, and so on.
- Typically uses a Queue (First-In, First-Out) to keep track of nodes to visit next.
- Finds the shortest path (in terms of number of edges) between the start node and all other reachable nodes in an unweighted graph.
- Algorithm:
  1. Enqueue the start node and mark it as visited.
  2. While the queue is not empty:
  3. Dequeue a node `u`.
  4. For each unvisited neighbor `v` of `u`:
  5. Mark `v` as visited and enqueue `v`.
Depth-First Search (DFS):
- Explores as far as possible along each branch before backtracking. It starts at a source node, explores one of its neighbors completely, then explores another neighbor completely, etc.
- Typically uses a Stack (Last-In, First-Out) - either implicitly via recursion or explicitly with a stack data structure - to keep track of nodes to visit next.
- Useful for topological sorting, finding connected components, cycle detection, and solving pathfinding problems (like mazes).
- Algorithm (Iterative):
  1. Push the start node onto the stack and mark it as visited.
  2. While the stack is not empty:
  3. Pop a node `u`.
  4. For each unvisited neighbor `v` of `u`:
  5. Mark `v` as visited and push `v` onto the stack.

Conceptual Pseudocode

function BFS(graph, startNode) {
    let queue = [startNode];
    let visited = new Set([startNode]);
    let traversalOrder = [];

    while (queue.length > 0) {
        let currentNode = queue.shift(); // Dequeue
        traversalOrder.push(currentNode);

        for (let neighbor of graph.getNeighbors(currentNode)) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor); // Enqueue
            }
        }
    }
    return traversalOrder;
}

function DFS_Iterative(graph, startNode) {
    let stack = [startNode];
    let visited = new Set(); // Visited when popped, or pushed?
    let traversalOrder = [];

    while (stack.length > 0) {
        let currentNode = stack.pop(); // Pop

        if (!visited.has(currentNode)) {
             visited.add(currentNode);
             traversalOrder.push(currentNode);

             // Push neighbors in reverse order for typical DFS result
             let neighbors = graph.getNeighbors(currentNode).reverse();
             for (let neighbor of neighbors) {
                 if (!visited.has(neighbor)) {
                     stack.push(neighbor); // Push
                 }
             }
        }
    }
    return traversalOrder;
}