Coding Patterns
Graph Traversal
Code Templates

Code Templates

Ready to implement graph traversal algorithms? These templates provide standardized, memorizable code “blueprints” that you can adapt to most graph problems. Refer back to the Concept Guide for theory.

BFS Template

The most common graph traversal pattern for finding shortest paths in unweighted graphs. This template directly solves problems like Number of Islands and Clone Graph.

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

    while (queue.length > 0) {
        const current = queue.shift();
        result.push(current);

        for (const neighbor of graph[current] || []) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }

    return result;
}
from collections import deque
from typing import List, Dict, Set

def bfs(graph: Dict[str, List[str]], start_node: str) -> List[str]:
    queue = deque([start_node])
    visited = set([start_node])
    result = []

    while queue:
        current = queue.popleft()
        result.append(current)

        for neighbor in graph.get(current, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return result
import java.util.*;

public List<String> bfs(Map<String, List<String>> graph, String startNode) {
    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    List<String> result = new ArrayList<>();

    queue.add(startNode);
    visited.add(startNode);

    while (!queue.isEmpty()) {
        String current = queue.poll();
        result.add(current);

        for (String neighbor : graph.getOrDefault(current, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.add(neighbor);
            }
        }
    }

    return result;
}
#include <vector>
#include <queue>
#include <unordered_set>
#include <string>

using namespace std;

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

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

    while (!q.empty()) {
        string current = q.front();
        q.pop();
        result.push_back(current);

        if (graph.find(current) != graph.end()) {
            for (const string& neighbor : graph.at(current)) {
                if (visited.find(neighbor) == visited.end()) {
                    visited.insert(neighbor);
                    q.push(neighbor);
                }
            }
        }
    }

    return result;
}
package main

import (
    "container/list"
)

func bfs(graph map[string][]string, startNode string) []string {
    queue := list.New()
    visited := make(map[string]bool)
    var result []string

    queue.PushBack(startNode)
    visited[startNode] = true

    for queue.Len() > 0 {
        current := queue.Remove(queue.Front()).(string)
        result = append(result, current)

        for _, neighbor := range graph[current] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue.PushBack(neighbor)
            }
        }
    }

    return result
}
def bfs(graph, start_node)
    queue = [start_node]
    visited = Set.new([start_node])
    result = []

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

        (graph[current] || []).each do |neighbor|
          unless visited.include?(neighbor)
            visited.add(neighbor)
            queue.push(neighbor)
          end
        end
    end

    result
end

Code Breakdown

Key Variables

  • queue: Stores nodes to visit in FIFO order (BFS) or LIFO order (DFS)
  • visited: Prevents revisiting nodes and infinite loops
  • result: Collects nodes in traversal order
  • current: The node being processed

Visual Flow 

  flowchart TD;
    A[Start Node] --> B{Queue Empty?};
    B -->|No| C[Dequeue Current];
    C --> D[Add to Result];
    D --> E[Process Neighbors];
    E --> F{Neighbor Visited?};
    F -->|No| G[Mark Visited & Enqueue];
    F -->|Yes| H[Skip];
    G --> I[Next Neighbor];
    H --> I;
    I --> J{More Neighbors?};
    J -->|Yes| F;
    J -->|No| B;
    B -->|Yes| K[Return Result];

Critical Sections

  1. Initialization: Setup queue with start node, mark as visited
  2. Processing Loop: Continue until queue is empty
  3. Neighbor Handling: Check visited status before enqueuing
  4. Result Building: Add processed nodes to result array

DFS Recursive Template

Perfect for exploring all paths, cycle detection, and backtracking problems.

function dfs(graph, node, visited = new Set(), result = []) {
    visited.add(node);
    result.push(node);

    for (const neighbor of graph[node] || []) {
        if (!visited.has(neighbor)) {
            dfs(graph, neighbor, visited, result);
        }
    }

    return result;
}
from typing import List, Dict, Set

def dfs(graph: Dict[str, List[str]], node: str, visited: Set[str] = None, result: List[str] = None) -> List[str]:
    if visited is None:
        visited = set()
    if result is None:
        result = []

    visited.add(node)
    result.append(node)

    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            dfs(graph, neighbor, visited, result)

    return result
import java.util.*;

public class GraphTraversal {
    public void dfs(Map<String, List<String>> graph, String node, Set<String> visited, List<String> result) {
        visited.add(node);
        result.add(node);

        for (String neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfs(graph, neighbor, visited, result);
            }
        }
    }

    public List<String> dfsRecursive(Map<String, List<String>> graph, String startNode) {
        Set<String> visited = new HashSet<>();
        List<String> result = new ArrayList<>();
        dfs(graph, startNode, visited, result);
        return result;
    }
}
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <string>

using namespace std;

void dfs(const unordered_map<string, vector<string>>& graph, const string& node,
         unordered_set<string>& visited, vector<string>& result) {
    visited.insert(node);
    result.push_back(node);

    if (graph.find(node) != graph.end()) {
        for (const string& neighbor : graph.at(node)) {
            if (visited.find(neighbor) == visited.end()) {
                dfs(graph, neighbor, visited, result);
            }
        }
    }
}

vector<string> dfsRecursive(const unordered_map<string, vector<string>>& graph, const string& startNode) {
    unordered_set<string> visited;
    vector<string> result;
    dfs(graph, startNode, visited, result);
    return result;
}
package main

func dfs(graph map[string][]string, node string, visited map[string]bool, result *[]string) {
    visited[node] = true
    *result = append(*result, node)

    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            dfs(graph, neighbor, visited, result)
        }
    }
}

func dfsRecursive(graph map[string][]string, startNode string) []string {
    visited := make(map[string]bool)
    var result []string
    dfs(graph, startNode, visited, &result)
    return result
}
def dfs(graph, node, visited = Set.new, result = [])
  visited.add(node)
  result << node

  (graph[node] || []).each do |neighbor|
    unless visited.include?(neighbor)
      dfs(graph, neighbor, visited, result)
    end
  end

  result
end

Variations

Grid/Matrix Traversal

For 2D grid problems like Number of Islands:

function dfsGrid(grid, row, col, visited) {
    const rows = grid.length;
    const cols = grid[0].length;
    const key = `${row},${col}`;

    if (row < 0 || row >= rows || col < 0 || col >= cols ||
        visited.has(key) || grid[row][col] === '0') {
        return;
    }

    visited.add(key);

    // Visit 4 directions
    dfsGrid(grid, row + 1, col, visited);
    dfsGrid(grid, row - 1, col, visited);
    dfsGrid(grid, row, col + 1, visited);
    dfsGrid(grid, row, col - 1, visited);
}

BFS with Distance Tracking

For shortest path problems:

function bfsWithDistance(graph, startNode) {
    const queue = [{node: startNode, distance: 0}];
    const visited = new Set([startNode]);
    const distances = {[startNode]: 0};

    while (queue.length > 0) {
        const {node: current, distance} = queue.shift();

        for (const neighbor of graph[current] || []) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                distances[neighbor] = distance + 1;
                queue.push({node: neighbor, distance: distance + 1});
            }
        }
    }

    return distances;
}

Practice

Ready to apply these templates? Head over to our Practice Problems to solve real LeetCode questions using these patterns.

Pro Tip: Always mark nodes as visited BEFORE adding them to the queue/stack to prevent duplicates and improve performance. This is especially important in graphs with cycles.