Graphs

What you'll learn

What a graph is, how to store one with an adjacency list, and how breadth-first search (BFS) and depth-first search (DFS) visit every node.

Why it matters

Maps, social networks, the internet, game levels and dependencies between tasks are all graphs. Finding the shortest route or "who are my friends of friends" are graph problems.

Explanation

A graph is a set of nodes (also called vertices) connected by edges. Edges can be undirected (a friendship goes both ways) or directed (a one-way street).

The usual way to store a graph is an adjacency list: for each node, a list of its neighbours.

Two ways to visit every reachable node:

• BFS (breadth-first search): visit the start, then all its neighbours, then their neighbours, level by level. It uses a queue and finds the shortest path in an unweighted graph.
• DFS (depth-first search): go as deep as possible along one path, then back up. It uses a stack (or recursion).

Both keep a visited set so they never loop forever in a cycle. Time complexity is O(V + E): each node and each edge is looked at once.

Example

Step-by-step walkthrough

1. The graph has five nodes. D connects to B, C and E.
2. BFS from A: visit A. Queue its neighbours B and C. Visit B (queue D), visit C, visit D (queue E), visit E. Order: A B C D E.
3. DFS from A: visit A, go to its first neighbour B, then B's unvisited neighbour D, then D's neighbours: C first, then E. Order: A B D C E.
4. shortestPath is BFS that keeps whole paths in the queue. The first path to reach E is the shortest: A -> B -> D -> E.
5. The visited set stops us walking A -> B -> A -> B forever.

Try it yourself

Add a new node F connected to E, then check the BFS order and the path from A to F.

BFS and DFSJavaScript

Editable codeconst graph = { A: ["B", "C"], B: ["A", "D"], C: ["A", "D"], D: ["B", "C", "E"], E: ["D"], }; function bfs(start) { const visited = new Set([start]); const queue = [start]; const order = []; while (queue.length > 0) { const node = queue.shift(); order.push(node); for (const next of graph[node]) { if (!visited.has(next)) { visited.add(next); queue.push(next); } } } return order; } console.log(bfs("A").join(" "));

Run ResetCopyCtrl+Enter to run

Common mistakes

• No visited set, which loops forever on cycles.
• Marking nodes visited too late in BFS, so a node can be queued twice. Mark when you enqueue.
• Forgetting undirected edges go both ways when building the list.
• Using DFS to find the shortest path. DFS does not guarantee it; BFS does (in unweighted graphs).

Quick quiz

Summary

• A graph is nodes plus edges, usually stored as an adjacency list.
• BFS (queue) explores level by level and finds shortest paths; DFS (stack or recursion) goes deep first.
• Both are O(V + E) and need a visited set.

Next: dynamic programming.

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C"],
};

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C", "E"],
  E: ["D"],
};

function bfs(start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
    for (const next of graph[node]) {
      if (!visited.has(next)) {
        visited.add(next);
        queue.push(next);
      }
    }
  }
  return order;
}

function dfs(node, visited = new Set(), order = []) {
  visited.add(node);
  order.push(node);
  for (const next of graph[node]) {
    if (!visited.has(next)) dfs(next, visited, order);
  }
  return order;
}

function shortestPath(start, goal) {
  const queue = [[start]];
  const seen = new Set([start]);
  while (queue.length > 0) {
    const path = queue.shift();
    const node = path[path.length - 1];
    if (node === goal) return path;
    for (const next of graph[node]) {
      if (!seen.has(next)) {
        seen.add(next);
        queue.push([...path, next]);
      }
    }
  }
  return null;
}

console.log(bfs("A").join(" "));
console.log(dfs("A").join(" "));
console.log(shortestPath("A", "E").join(" -> "));