Graphs

Why graphs matter

Now that we've covered Trees, we're ready for a structure that removes the biggest tree restriction: a node no longer needs exactly one parent path from the root.

A graph models relationships:

• users connected by friendships
• cities connected by roads
• accounts connected by transfers
• web pages connected by links
• tasks connected by dependencies

Trees are a special, tidy kind of graph. Graphs are the more general tool for messy real-world connections.

The core pieces

A graph is made of:

• Vertices, also called nodes: the things being connected
• Edges: the relationships between those things

A ----- B
|       |
C ----- D

Here, A, B, C, and D are vertices. The lines are edges.

Important graph flavors

• Undirected graph: edges work both ways, like mutual friendship
• Directed graph: edges have direction, like a follow or dependency
• Weighted graph: edges have costs, like distance or time
• Cyclic graph: you can follow edges and return to a previous node

Unlike trees, graphs often contain cycles, so traversal needs extra care.

Which statement best explains how graphs extend the tree model you learned in the previous lesson?

Common graph representations

There are three classic ways to store graph data:

1. Edge list

A list of connections:

[A, B], [A, C], [B, D]

Simple, but finding all neighbors of a node can be slow.

2. Adjacency matrix

A grid where matrix[i][j] tells whether i connects to j.

Good for dense graphs, but can waste space when most nodes are not connected.

3. Adjacency list

Each node stores its direct neighbors.

This is the most common representation for easy and medium graph problems because it is compact and practical.

```javascript
const graph = new Map();

function addUndirectedEdge(a, b) {
  if (!graph.has(a)) graph.set(a, []);
  if (!graph.has(b)) graph.set(b, []);

  graph.get(a).push(b);
  graph.get(b).push(a);
}

addUndirectedEdge('A', 'B');
addUndirectedEdge('A', 'C');
addUndirectedEdge('B', 'D');
addUndirectedEdge('C', 'D');

console.log('Neighbors of A:', graph.get('A'));

for (const [node, neighbors] of graph) {
  console.log(`${node}: ${neighbors.join(', ')}`);
}
```

True or false: An adjacency matrix is always more memory efficient than an adjacency list for a graph with many nodes but relatively few edges.

Visiting connected nodes

Graph traversal means starting at one node and exploring reachable nodes.

You already know the key building blocks from earlier lessons:

• Queues from Stacks and Queues power breadth-first search
• Stacks or recursion power depth-first search
• Tree traversal gives the idea of walking connected structures

The graph-specific twist is the visited set. Since graphs can contain cycles, we must remember where we've already been.

BFS explores in layers

Breadth-first search, or BFS, visits nodes by distance from the start:

Start
then all 1-edge neighbors
then all 2-edge neighbors
then all 3-edge neighbors
...

This makes BFS especially useful when you need the fewest number of edges in an unweighted graph.

The queue keeps the order fair: first discovered, first explored.

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

function bfs(start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];
  let head = 0;

  while (head < queue.length) {
    const node = queue[head++];
    order.push(node);

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

  return order;
}

console.log(bfs('A').join(' -> '));
```

A graph traversal typically keeps a ______ set so it does not loop forever when the graph contains cycles.

DFS follows a path deeply

Depth-first search, or DFS, explores one path as far as it can before backing up.

This feels similar to recursive tree traversal from the Trees lesson, but with one important addition: the visited set.

DFS is useful for questions like:

• Can I reach this node?
• How many connected groups are there?
• Does a path exist between two nodes?

For easy and medium graph problems, the main skill is choosing whether BFS or DFS matches the shape of the question.

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

function dfs(start) {
  const visited = new Set();
  const order = [];

  function visit(node) {
    if (visited.has(node)) return;

    visited.add(node);
    order.push(node);

    for (const neighbor of graph[node]) {
      visit(neighbor);
    }
  }

  visit(start);
  return order;
}

console.log(dfs('A').join(' -> '));
```

You are given an unweighted graph of city connections and need the minimum number of roads from city A to city Z. Which traversal is usually the best first choice?

What to recognize

Many easy and medium graph problems reduce to a few patterns:

• Reachability: can one node get to another?
• Connected components: how many separate groups exist?
• Shortest hops: what is the fewest number of edges?
• Cycle detection: can we return to a node through edges?

Mental checklist

When you see a graph problem, ask:

1. Are edges directed or undirected?
2. Are edges weighted or unweighted?
3. What representation makes neighbor lookup easy?
4. Do I need BFS layers or DFS depth?
5. Where will I store visited nodes?

Next, we'll look at Hash Tables, which will strengthen your understanding of fast lookup structures like the sets and maps we used here.