Graph Traversal Algorithms - Complete Guide

Graph traversal is fundamental for solving many algorithmic problems. This guide covers depth-first search (DFS), breadth-first search (BFS), and their applications.

Graph Representation #

Adjacency List #

// Undirected graph
const graph = {
  0: [1, 2],
  1: [0, 2, 3],
  2: [0, 1, 4],
  3: [1, 4],
  4: [2, 3]
};

// Directed graph
const directedGraph = {
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['D', 'E'],
  'D': [],
  'E': []
};

// Weighted graph
const weightedGraph = {
  'A': [{ node: 'B', weight: 4 }, { node: 'C', weight: 2 }],
  'B': [{ node: 'D', weight: 3 }],
  'C': [{ node: 'D', weight: 1 }],
  'D': []
};

Adjacency Matrix #

// 0 1 2 3 4
const matrix = [
  [0, 1, 1, 0, 0],  // 0
  [1, 0, 1, 1, 0],  // 1
  [1, 1, 0, 0, 1],  // 2
  [0, 1, 0, 0, 1],  // 3
  [0, 0, 1, 1, 0]   // 4
];

// Check if edge exists
const hasEdge = matrix[0][1] === 1;  // true

Edge List #

const edges = [
  [0, 1],
  [0, 2],
  [1, 2],
  [1, 3],
  [2, 4],
  [3, 4]
];

Depth-First Search (DFS) #

Recursive DFS #

function dfs(graph, start, visited = new Set()) {
  console.log(start);
  visited.add(start);

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

// Usage
const graph = {
  0: [1, 2],
  1: [0, 2, 3],
  2: [0, 1, 4],
  3: [1, 4],
  4: [2, 3]
};

dfs(graph, 0);
// Output: 0, 1, 2, 4, 3

Iterative DFS #

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

  while (stack.length > 0) {
    const node = stack.pop();

    if (!visited.has(node)) {
      console.log(node);
      visited.add(node);

      // Add neighbors in reverse order for same traversal as recursive
      for (let i = graph[node].length - 1; i >= 0; i--) {
        const neighbor = graph[node][i];
        if (!visited.has(neighbor)) {
          stack.push(neighbor);
        }
      }
    }
  }
}

dfsIterative(graph, 0);

DFS with Path Tracking #

function dfsPath(graph, start, end, visited = new Set(), path = []) {
  visited.add(start);
  path.push(start);

  if (start === end) {
    return path;
  }

  for (const neighbor of graph[start] || []) {
    if (!visited.has(neighbor)) {
      const result = dfsPath(graph, neighbor, end, visited, path);
      if (result) return result;
    }
  }

  path.pop();
  return null;
}

console.log(dfsPath(graph, 0, 3));
// [0, 1, 3]

All Paths #

function allPaths(graph, start, end, visited = new Set(), path = [], paths = []) {
  visited.add(start);
  path.push(start);

  if (start === end) {
    paths.push([...path]);
  } else {
    for (const neighbor of graph[start] || []) {
      if (!visited.has(neighbor)) {
        allPaths(graph, neighbor, end, visited, path, paths);
      }
    }
  }

  path.pop();
  visited.delete(start);

  return paths;
}

console.log(allPaths(graph, 0, 4));
// [[0, 1, 2, 4], [0, 1, 3, 4], [0, 2, 4]]

Breadth-First Search (BFS) #

Basic BFS #

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

  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node);

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

bfs(graph, 0);
// Output: 0, 1, 2, 3, 4

BFS Shortest Path #

function bfsShortestPath(graph, start, end) {
  const visited = new Set();
  const queue = [[start, [start]]];
  visited.add(start);

  while (queue.length > 0) {
    const [node, path] = queue.shift();

    if (node === end) {
      return path;
    }

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

  return null;
}

console.log(bfsShortestPath(graph, 0, 4));
// [0, 2, 4]

BFS Level Order #

function bfsLevelOrder(graph, start) {
  const visited = new Set();
  const queue = [[start, 0]];
  const levels = {};
  visited.add(start);

  while (queue.length > 0) {
    const [node, level] = queue.shift();

    if (!levels[level]) {
      levels[level] = [];
    }
    levels[level].push(node);

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

  return Object.values(levels);
}

console.log(bfsLevelOrder(graph, 0));
// [[0], [1, 2], [3, 4]]

Cycle Detection #

Undirected Graph (DFS) #

function hasCycleDFS(graph) {
  const visited = new Set();

  function dfs(node, parent) {
    visited.add(node);

    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, node)) {
          return true;
        }
      } else if (neighbor !== parent) {
        return true;  // Back edge found
      }
    }

    return false;
  }

  for (const node in graph) {
    if (!visited.has(node)) {
      if (dfs(node, null)) {
        return true;
      }
    }
  }

  return false;
}

console.log(hasCycleDFS(graph));  // true

Directed Graph (DFS) #

function hasCycleDirected(graph) {
  const WHITE = 0;  // Unvisited
  const GRAY = 1;   // Visiting
  const BLACK = 2;  // Visited

  const colors = {};

  for (const node in graph) {
    colors[node] = WHITE;
  }

  function dfs(node) {
    colors[node] = GRAY;

    for (const neighbor of graph[node] || []) {
      if (colors[neighbor] === GRAY) {
        return true;  // Back edge - cycle found
      }

      if (colors[neighbor] === WHITE && dfs(neighbor)) {
        return true;
      }
    }

    colors[node] = BLACK;
    return false;
  }

  for (const node in graph) {
    if (colors[node] === WHITE) {
      if (dfs(node)) {
        return true;
      }
    }
  }

  return false;
}

Topological Sort #

DFS Approach #

function topologicalSort(graph) {
  const visited = new Set();
  const stack = [];

  function dfs(node) {
    visited.add(node);

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

    stack.push(node);
  }

  for (const node in graph) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return stack.reverse();
}

const dag = {
  'A': ['C'],
  'B': ['C', 'D'],
  'C': ['E'],
  'D': ['F'],
  'E': ['F'],
  'F': []
};

console.log(topologicalSort(dag));
// ['B', 'D', 'A', 'C', 'E', 'F']

Kahn’s Algorithm (BFS) #

function topologicalSortBFS(graph) {
  const inDegree = {};
  const queue = [];
  const result = [];

  // Calculate in-degrees
  for (const node in graph) {
    if (!(node in inDegree)) {
      inDegree[node] = 0;
    }

    for (const neighbor of graph[node]) {
      inDegree[neighbor] = (inDegree[neighbor] || 0) + 1;
    }
  }

  // Add nodes with 0 in-degree
  for (const node in inDegree) {
    if (inDegree[node] === 0) {
      queue.push(node);
    }
  }

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

    for (const neighbor of graph[node] || []) {
      inDegree[neighbor]--;

      if (inDegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  // Check for cycle
  if (result.length !== Object.keys(graph).length) {
    throw new Error('Graph has a cycle');
  }

  return result;
}

console.log(topologicalSortBFS(dag));

Connected Components #

function countComponents(n, edges) {
  const graph = Array(n).fill(0).map(() => []);

  // Build graph
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u);
  }

  const visited = new Set();
  let count = 0;

  function dfs(node) {
    visited.add(node);

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

  for (let i = 0; i < n; i++) {
    if (!visited.has(i)) {
      count++;
      dfs(i);
    }
  }

  return count;
}

console.log(countComponents(5, [[0, 1], [1, 2], [3, 4]]));  // 2

Bipartite Graph #

Check if graph can be colored with 2 colors.

function isBipartite(graph) {
  const colors = {};

  function bfs(start) {
    const queue = [start];
    colors[start] = 0;

    while (queue.length > 0) {
      const node = queue.shift();

      for (const neighbor of graph[node] || []) {
        if (!(neighbor in colors)) {
          colors[neighbor] = 1 - colors[node];
          queue.push(neighbor);
        } else if (colors[neighbor] === colors[node]) {
          return false;  // Same color - not bipartite
        }
      }
    }

    return true;
  }

  for (const node in graph) {
    if (!(node in colors)) {
      if (!bfs(node)) {
        return false;
      }
    }
  }

  return true;
}

const bipartiteGraph = {
  0: [1, 3],
  1: [0, 2],
  2: [1, 3],
  3: [0, 2]
};

console.log(isBipartite(bipartiteGraph));  // true

Shortest Path (Unweighted) #

function shortestPath(graph, start, end) {
  const visited = new Set();
  const queue = [[start, 0]];
  visited.add(start);

  while (queue.length > 0) {
    const [node, distance] = queue.shift();

    if (node === end) {
      return distance;
    }

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

  return -1;  // No path
}

console.log(shortestPath(graph, 0, 4));  // 2

Clone Graph #

class Node {
  constructor(val, neighbors = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}

function cloneGraph(node) {
  if (!node) return null;

  const visited = new Map();

  function dfs(node) {
    if (visited.has(node)) {
      return visited.get(node);
    }

    const clone = new Node(node.val);
    visited.set(node, clone);

    for (const neighbor of node.neighbors) {
      clone.neighbors.push(dfs(neighbor));
    }

    return clone;
  }

  return dfs(node);
}

Course Schedule #

function canFinish(numCourses, prerequisites) {
  const graph = Array(numCourses).fill(0).map(() => []);

  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
  }

  const WHITE = 0;
  const GRAY = 1;
  const BLACK = 2;
  const colors = new Array(numCourses).fill(WHITE);

  function hasCycle(node) {
    colors[node] = GRAY;

    for (const neighbor of graph[node]) {
      if (colors[neighbor] === GRAY) {
        return true;
      }

      if (colors[neighbor] === WHITE && hasCycle(neighbor)) {
        return true;
      }
    }

    colors[node] = BLACK;
    return false;
  }

  for (let i = 0; i < numCourses; i++) {
    if (colors[i] === WHITE && hasCycle(i)) {
      return false;
    }
  }

  return true;
}

console.log(canFinish(2, [[1, 0]]));  // true
console.log(canFinish(2, [[1, 0], [0, 1]]));  // false

Word Ladder #

function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);

  if (!wordSet.has(endWord)) return 0;

  const queue = [[beginWord, 1]];
  const visited = new Set([beginWord]);

  while (queue.length > 0) {
    const [word, level] = queue.shift();

    if (word === endWord) {
      return level;
    }

    // Try all possible one-letter changes
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) {  // a-z
        const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);

        if (wordSet.has(newWord) && !visited.has(newWord)) {
          visited.add(newWord);
          queue.push([newWord, level + 1]);
        }
      }
    }
  }

  return 0;
}

console.log(ladderLength('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog']));
// 5 (hit -> hot -> dot -> dog -> cog)

Time Complexity #

Algorithm	Time Complexity	Space Complexity
DFS	O(V + E)	O(V)
BFS	O(V + E)	O(V)
Topological Sort	O(V + E)	O(V)
Cycle Detection	O(V + E)	O(V)

V = vertices, E = edges

DFS vs BFS #

Use DFS when:

Finding paths
Topological sorting
Detecting cycles
Backtracking problems
Tree traversals

Use BFS when:

Shortest path (unweighted)
Level-order traversal
Finding connected components
Minimum steps problems

Best Practices #

Choose right representation - Adjacency list for sparse, matrix for dense
Track visited - Prevent infinite loops
Use appropriate traversal - DFS for paths, BFS for shortest
Handle disconnected graphs - Loop through all nodes
Consider space - DFS uses stack, BFS uses queue
Optimize for problem - Sometimes custom traversal needed
Test edge cases - Empty graph, single node, cycles

Graph traversal is fundamental for many algorithms. Master DFS and BFS to solve complex graph problems efficiently.