Graphs

A graph is a set of things and the connections between them: cities and roads, people and friendships, tasks and the tasks they depend on. Trees, lists and grids are all special graphs. Before you can search one, you have to store it.

1. What it is

A graph has nodes (also called vertices) and edges joining pairs of nodes.

• Undirected: an edge works both ways (friendship). Directed: an edge has a direction (follows, depends on).
• Weighted: each edge carries a number (distance, cost, time).
• Neighbours of a node: the nodes joined to it. Its degree: how many neighbours it has (in directed graphs, in-degree and out-degree).
• Path: a route along edges. Cycle: a path that returns to where it started. A tree is a connected graph with no cycles.

2. How it sits in memory

Problems usually give a graph as a list of edges: [[0, 1], [0, 2], [1, 2], [2, 3]]. Searching needs "who are my neighbours?" quickly, so the first job is almost always converting the edges into an adjacency list: for each node, the list of its neighbours.

A grid is a graph too: each cell is a node, and its up, down, left and right cells are its neighbours. You don't build anything; the neighbour loop from arrays (structure 01) is the adjacency list.

3. Operations and what they cost

V is the number of nodes and E the number of edges. Visiting a whole graph with depth-first or breadth-first search is O(V + E) with an adjacency list.

4. In Python, TypeScript and Java

An adjacency list is just a hash map (or a list of lists when nodes are numbered 0 to n − 1).

from collections import defaultdict
    edges = [[0, 1], [0, 2], [1, 2], [2, 3]]
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)        # undirected: both directions
    print(graph[2])               # [0, 1, 3]

    weighted = defaultdict(list)  # neighbour and weight
    weighted["A"].append(("B", 5))

const edges = [[0, 1], [0, 2], [1, 2], [2, 3]];
    const n = 4;
    const graph: number[][] = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
      graph[u].push(v);
      graph[v].push(u);            // undirected
    }
    console.log(graph[2]);         // [0, 1, 3]

int n = 4;
    int[][] edges = {{0, 1}, {0, 2}, {1, 2}, {2, 3}};
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] e : edges) {
        graph.get(e[0]).add(e[1]);
        graph.get(e[1]).add(e[0]);   // undirected
    }
    System.out.println(graph.get(2));   // [0, 1, 3]

5. Core operations, step by step

Three things to do with a graph before (or instead of) searching it.

def build_graph(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    return graph

function buildGraph(n: number, edges: number[][]): number[][] {
  const graph: number[][] = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u);
  }
  return graph;
}

static List<List<Integer>> buildGraph(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] e : edges) {
        graph.get(e[0]).add(e[1]);
        graph.get(e[1]).add(e[0]);
    }
    return graph;
}

def in_degrees(n, edges):
    indeg = [0] * n
    for u, v in edges:
        indeg[v] += 1
    return indeg

function inDegrees(n: number, edges: number[][]): number[] {
  const indeg = new Array(n).fill(0);
  for (const [u, v] of edges) {
    indeg[v] += 1;
  }
  return indeg;
}

static int[] inDegrees(int n, int[][] edges) {
    int[] indeg = new int[n];
    for (int[] e : edges) {
        indeg[e[1]] += 1;
    }
    return indeg;
}

def build_matrix(n, edges):
    m = [[0] * n for _ in range(n)]
    for u, v in edges:
        m[u][v] = 1
        m[v][u] = 1
    return m

function buildMatrix(n: number, edges: number[][]): number[][] {
  const m = Array.from({ length: n }, () => new Array(n).fill(0));
  for (const [u, v] of edges) {
    m[u][v] = 1;
    m[v][u] = 1;
  }
  return m;
}

static int[][] buildMatrix(int n, int[][] edges) {
    int[][] m = new int[n][n];
    for (int[] e : edges) {
        m[e[0]][e[1]] = 1;
        m[e[1]][e[0]] = 1;
    }
    return m;
}

6. How to remember it

7. Problems solved with it

Two easy problems solved by building the right representation, no searching needed.

def find_center(edges):
    a, b = edges[0]
    c, d = edges[1]
    if a == c or a == d:
        return a
    return b

function findCenter(edges: number[][]): number {
  const [a, b] = edges[0];
  const [c, d] = edges[1];
  if (a === c || a === d) {
    return a;
  }
  return b;
}

static int findCenter(int[][] edges) {
    int a = edges[0][0], b = edges[0][1];
    int c = edges[1][0], d = edges[1][1];
    if (a == c || a == d) {
        return a;
    }
    return b;
}

def find_judge(n, trust):
    score = [0] * (n + 1)
    for a, b in trust:
        score[a] -= 1
        score[b] += 1
    for person in range(1, n + 1):
        if score[person] == n - 1:
            return person
    return -1

function findJudge(n: number, trust: number[][]): number {
  const score = new Array(n + 1).fill(0);
  for (const [a, b] of trust) {
    score[a] -= 1;
    score[b] += 1;
  }
  for (let person = 1; person <= n; person++) {
    if (score[person] === n - 1) {
      return person;
    }
  }
  return -1;
}

static int findJudge(int n, int[][] trust) {
    int[] score = new int[n + 1];
    for (int[] t : trust) {
        score[t[0]] -= 1;
        score[t[1]] += 1;
    }
    for (int person = 1; person <= n; person++) {
        if (score[person] == n - 1) {
            return person;
        }
    }
    return -1;
}

More practice, solved on the pattern pages

8. Common mistakes

9. Self-check quiz

10. Where it shows up next

• 11 · DFS: go deep first; connected components, cycles and ordering tasks.
• 12 · BFS: explore ring by ring; shortest paths when every edge costs the same.
• 13 · Matrix Traversal: grids as graphs: islands, flood fill, rotting oranges.
• 20 · Shortest Path & MST: weighted graphs with Dijkstra and minimum spanning trees.
• 23 · Union-Find: which nodes are connected, as edges arrive.

Last stop before the patterns: 12 · Choosing a structure.