Graphs

Why Graphs?

Graphs model relationships. Social networks (who follows whom), maps (roads between cities), dependency trees (build order), web pages (links) — all graphs. If your problem involves connections between things, you’re dealing with a graph.

Representing Graphs

// Adjacency list — most common, space-efficient
type Graph = Map<string, string[]>;

function buildGraph(edges: [string, string][]): Graph {
  const graph: Graph = new Map();

  for (const [from, to] of edges) {
    if (!graph.has(from)) graph.set(from, []);
    if (!graph.has(to)) graph.set(to, []);
    graph.get(from)!.push(to);
    graph.get(to)!.push(from); // omit for directed graph
  }
  return graph;
}

DFS and BFS on Graphs

// DFS — go deep, then backtrack
function dfs(graph: Graph, start: string): string[] {
  const visited = new Set<string>();
  const result: string[] = [];

  function visit(node: string) {
    if (visited.has(node)) return;
    visited.add(node);
    result.push(node);
    for (const neighbor of graph.get(node) || []) {
      visit(neighbor);
    }
  }

  visit(start);
  return result;
}

// BFS — explore level by level
function bfs(graph: Graph, start: string): string[] {
  const visited = new Set<string>([start]);
  const queue: string[] = [start];
  const result: string[] = [];

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

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

Topological Sort

Order nodes so that every directed edge goes from earlier to later. Used for build systems, course prerequisites, task scheduling.

function topologicalSort(graph: Map<string, string[]>): string[] {
  const visited = new Set<string>();
  const result: string[] = [];

  function dfs(node: string) {
    if (visited.has(node)) return;
    visited.add(node);
    for (const neighbor of graph.get(node) || []) {
      dfs(neighbor);
    }
    result.push(node); // add after all dependencies
  }

  for (const node of graph.keys()) {
    dfs(node);
  }

  return result.reverse();
}

Key Takeaways

1. Adjacency lists are the go-to representation — space-efficient and easy to traverse
2. Always track visited nodes to avoid infinite loops in graphs with cycles
3. BFS finds shortest paths in unweighted graphs; DFS explores all paths
4. Topological sort is essential for dependency resolution