Algorithms Lesson 8: Graphs

Graphs model connections: social networks, maps, web pages, dependencies. DFS and BFS are the two fundamental graph traversal algorithms.

Graph Representations

// Adjacency List (most common)
const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"]
};

// Adjacency Matrix (dense graphs)
const matrix = [
  // A  B  C
  [  0, 1, 1 ],  // A connects to B and C
  [  1, 0, 0 ],  // B connects to A
  [  1, 0, 0 ]   // C connects to A
];

DFS & BFS

// DFS — Depth First Search (explores deep)
function dfs(graph, start, visited = new Set()) {
  visited.add(start);
  const result = [start];
  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      result.push(...dfs(graph, neighbor, visited));
    }
  }
  return result;
}

// BFS — Breadth First Search (finds shortest path!)
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const result = [];
  while (queue.length) {
    const node = queue.shift();
    result.push(node);
    for (const n of graph[node]) {
      if (!visited.has(n)) { visited.add(n); queue.push(n); }
    }
  }
  return result;
}

// Shortest path between two nodes:
function shortestPath(graph, start, end) {
  const queue = [[start, [start]]];
  const visited = new Set([start]);
  while (queue.length) {
    const [node, path] = queue.shift();
    if (node === end) return path;
    for (const n of graph[node]) {
      if (!visited.has(n)) {
        visited.add(n);
        queue.push([n, [...path, n]]);
      }
    }
  }
  return null;
}