Graph Traversal: BFS and DFS Code Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Graph Traversal: Complete Guide with BFS and DFS Examples

The concept guide covers when to reach for BFS versus DFS and why the visited check matters. This page gives you the code in a form you can memorize and adapt. The main template is BFS on an adjacency list, and every template below runs in

O(V + E)

time with

O(V)

extra space unless otherwise noted.

Main Template: BFS on an Adjacency List

This is the most common graph traversal template. It visits nodes in layers, and it is the right starting point for shortest path, level counting, and multi-source problems. The visited set does double duty. It prevents infinite loops in cyclic graphs and guarantees that each node is discovered exactly once.

Use this for Clone Graph and Rotting Oranges .

function bfs(graph, start) {
    const queue = [start];
    const visited = new Set([start]);
    const result = [];

    while (queue.length > 0) {
        const node = queue.shift();
        result.push(node);
        // Mark neighbors on the way in. A node that is already
        // marked was discovered on an earlier layer, so it is
        // skipped and never enters the queue twice.
        for (const neighbor of graph[node] || []) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return result;
}

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = {start}
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        # The visited check runs before enqueueing, not after
        # dequeuing. That keeps the queue at one entry per node
        # instead of one entry per edge.
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return result

List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    List<Integer> result = new ArrayList<>();

    queue.offer(start);
    visited.add(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);
        // Marking at discovery time is what keeps the layers
        // clean. A neighbor found by two nodes in the same
        // layer only enters the queue once.
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
    return result;
}

vector<int> bfs(const unordered_map<int, vector<int>>& graph, int start) {
    queue<int> q;
    unordered_set<int> visited;
    vector<int> result;

    q.push(start);
    visited.insert(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        result.push_back(node);
        // Check the map once, then scan the neighbor list.
        // Nodes are marked here, at enqueue time, so cyclic
        // graphs terminate and layers stay correct.
        if (graph.find(node) != graph.end()) {
            for (int neighbor : graph.at(node)) {
                if (visited.find(neighbor) == visited.end()) {
                    visited.insert(neighbor);
                    q.push(neighbor);
                }
            }
        }
    }
    return result;
}

func bfs(graph map[int][]int, start int) []int {
    queue := []int{start}
    visited := map[int]bool{start: true}
    result := []int{}

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node)
        // Reading a missing key returns nil, so the neighbor
        // loop is safe without a lookup. The visited map is
        // set before a node is appended to the queue.
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }
    return result
}

def bfs(graph, start)
    queue = [start]
    visited = Set.new([start])
    result = []

    until queue.empty?
        node = queue.shift
        result << node

        # Marking happens here, at discovery time. If it
        # happened at processing time, a node reachable from
        # several neighbors would be queued several times.
        (graph[node] || []).each do |neighbor|
            unless visited.include?(neighbor)
                visited.add(neighbor)
                queue.push(neighbor)
            end
        end
    end

    result
end

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

queue: nodes waiting to be processed, in discovery order. This container is the only difference between BFS and DFS.
visited: the set of nodes that have been enqueued. It prevents infinite loops and keeps every node in the queue exactly once.
result: the traversal order. Some problems do not need this list, only the visits themselves.
node: the current node. All the work for one step happens here. Record it, then look at its neighbors.

Visual Mechanism

    stateDiagram-v2
    [*] --> Init: enqueue start, mark visited
    Init --> Loop: queue not empty
    Loop --> Process: dequeue node
    Process --> Neighbors: scan neighbor list
    Neighbors --> Mark: neighbor unvisited
    Mark --> Neighbors: mark and enqueue
    Neighbors --> Loop: no unvisited neighbors left
    Loop --> Done: queue empty
    Done --> [*]

Critical Sections

The initialization is where the visited set is born. The start node is marked in the same step it is enqueued. Missing this one line turns a cyclic graph into an infinite loop, and it is the first thing interviewers check in a BFS.

The neighbor loop is where layers stay correct. Each neighbor is checked against the set, marked, and enqueued. Because marking happens before the node is processed, two neighbors of the same node cannot both enqueue it, and the queue only ever holds one copy of each node.

The termination condition is structural. The loop ends when the queue is empty, which means every node reachable from the start has been visited. Nodes outside the start’s component never appear, which is why connected-component problems wrap this loop in an outer loop over all nodes.

Variations

1. Recursive DFS

The same skeleton, but the call stack replaces the explicit stack. This is the template for connectivity, flood fill, and enumeration problems. The recursion depth is the risk. Use the iterative version when the graph can be deep.

Use this for Flood Fill and Pacific Atlantic Water Flow .

function dfs(graph, node, visited = new Set(), result = []) {
    visited.add(node);
    result.push(node);
    // The call stack holds the search path. Backtracking
    // happens automatically when a node runs out of neighbors
    // and the function returns to its caller.
    for (const neighbor of graph[node] || []) {
        if (!visited.has(neighbor)) {
            dfs(graph, neighbor, visited, result);
        }
    }
    return result;
}

def dfs(graph, node, visited=None, result=None):
    if visited is None:
        visited = set()
    if result is None:
        result = []

    visited.add(node)
    result.append(node)
    # Mutable defaults are shared across calls, so they are
    # created per call instead. Each recursive frame is one
    # stack entry, and the returns are the backtracking.
    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            dfs(graph, neighbor, visited, result)

    return result

void dfs(Map<Integer, List<Integer>> graph, int node,
         Set<Integer> visited, List<Integer> result) {
    visited.add(node);
    result.add(node);
    // Every frame is one node on the search path. When a node
    // has no new neighbors, the function returns and the path
    // unwinds to the previous node.
    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        if (!visited.contains(neighbor)) {
            dfs(graph, neighbor, visited, result);
        }
    }
}

List<Integer> dfsFrom(Map<Integer, List<Integer>> graph, int start) {
    Set<Integer> visited = new HashSet<>();
    List<Integer> result = new ArrayList<>();
    dfs(graph, start, visited, result);
    return result;
}

void dfs(const unordered_map<int, vector<int>>& graph, int node,
         unordered_set<int>& visited, vector<int>& result) {
    visited.insert(node);
    result.push_back(node);
    // Frames push and pop with the recursion. A node that runs
    // out of neighbors returns, and control hands back to the
    // frame that discovered it.
    if (graph.find(node) != graph.end()) {
        for (int neighbor : graph.at(node)) {
            if (visited.find(neighbor) == visited.end()) {
                dfs(graph, neighbor, visited, result);
            }
        }
    }
}

vector<int> dfsFrom(const unordered_map<int, vector<int>>& graph, int start) {
    unordered_set<int> visited;
    vector<int> result;
    dfs(graph, start, visited, result);
    return result;
}

func dfs(graph map[int][]int, node int, visited map[int]bool, result *[]int) {
    visited[node] = true
    *result = append(*result, node)
    // The call stack does the backtracking. Every return frees
    // one frame and hands control back to the previous node,
    // which then tries its next neighbor.
    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            dfs(graph, neighbor, visited, result)
        }
    }
}

func dfsFrom(graph map[int][]int, start int) []int {
    visited := make(map[int]bool)
    result := []int{}
    dfs(graph, start, visited, &result)
    return result
}

def dfs(graph, node, visited = Set.new, result = [])
    visited.add(node)
    result << node

    # The Ruby runtime manages the stack. Each recursive call
    # dives one level deeper, and the returns walk back up the
    # path when a node is fully explored.
    (graph[node] || []).each do |neighbor|
        dfs(graph, neighbor, visited, result) unless visited.include?(neighbor)
    end

    result
end

2. Iterative DFS

The recursive version is cleaner, but an explicit stack is safer on deep graphs. Marking happens at push time. Marking at pop time would let the same node sit on the stack in several branches.

function dfsIterative(graph, start) {
    const stack = [start];
    const visited = new Set([start]);
    const result = [];

    while (stack.length > 0) {
        const node = stack.pop();
        result.push(node);
        // Mark on push, not on pop. A node reachable from two
        // branches would otherwise be pushed once per branch.
        for (const neighbor of graph[node] || []) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                stack.push(neighbor);
            }
        }
    }
    return result;
}

def dfs_iterative(graph, start):
    stack = [start]
    visited = {start}
    result = []

    while stack:
        node = stack.pop()
        result.append(node)
        # Pushing all unvisited neighbors at once visits them
        # in reverse order later. That is a valid DFS order,
        # just not identical to the recursive version.
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)

    return result

3. Grid DFS (Flood Fill)

A grid is a graph where each cell has up to four neighbors. The only new work is the bounds check that runs before any access.

Use this for Flood Fill .

function floodFill(grid, sr, sc, newColor) {
    const original = grid[sr][sc];
    if (original === newColor) return grid;

    const rows = grid.length;
    const cols = grid[0].length;

    function fill(r, c) {
        // The bounds check must run before the value check.
        // The other order reads outside the grid and crashes.
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== original) return;
        grid[r][c] = newColor;
        fill(r + 1, c);
        fill(r - 1, c);
        fill(r, c + 1);
        fill(r, c - 1);
    }

    fill(sr, sc);
    return grid;
}

def flood_fill(grid, start_r, start_c, new_color):
    original = grid[start_r][start_c]
    if original == new_color:
        return grid

    rows, cols = len(grid), len(grid[0])

    def fill(r, c):
        # Four neighbors, each guarded by the same bounds and
        # color checks. Painting the cell before recursing is
        # what prevents the same cell from being visited again.
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != original:
            return
        grid[r][c] = new_color
        fill(r + 1, c)
        fill(r - 1, c)
        fill(r, c + 1)
        fill(r, c - 1)

    fill(start_r, start_c)
    return grid

4. BFS with Level Tracking

When a problem counts rounds or distances, drain the queue one layer at a time. The layer boundary is drawn by recording the queue size before processing.

Use this for Rotting Oranges .

function bfsLevels(graph, start) {
    const queue = [start];
    const visited = new Set([start]);
    const levels = [];

    while (queue.length > 0) {
        // Record the size once. The for loop drains exactly
        // the current layer, and everything pushed during the
        // loop forms the next layer.
        const size = queue.length;
        const layer = [];
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            layer.push(node);
            for (const neighbor of graph[node] || []) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push(neighbor);
                }
            }
        }
        levels.push(layer);
    }

    return levels;
}

from collections import deque

def bfs_levels(graph, start):
    queue = deque([start])
    visited = {start}
    levels = []

    while queue:
        # Snapshot the layer. Everything in the queue right now
        # is the same distance from the start, and each of them
        # spawns the next layer while this one drains.
        layer = []
        for _ in range(len(queue)):
            node = queue.popleft()
            layer.append(node)
            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        levels.append(layer)

    return levels

Each variation above is a separate review card in the app. Drill them individually so you do not mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .