Graphs for Coding Interviews: A Crash Course

1. Vertex

A single point in the graph. 0, 1, 2 and 3 are vertices.

Vertices usually hold the data, such as a person or a city.

2. Edge

A connection between two vertices.

Edges can be directed or undirected. The highlighted edges are 0-1 and 0-2.

3. Directed

Every edge points one way, like a one way street.

Here you can go from 0 to 1, but not from 1 back to 0.

4. Undirected

Edges have no direction, so you can travel both ways.

From 0 you can reach 1, and from 1 you can return to 0.

5. Indegree

The number of edges pointing into a vertex.

Two edges point into 3: from 1 and from 2.

Indegree of 3 is 2.

6. Outdegree

The number of edges leaving a vertex.

Two edges leave 0: to 1 and to 2.

Outdegree of 0 is 2.

7. Connected

There is a path between every pair of vertices.

The path does not have to be a single edge.

0 reaches 4 through 1.

8. Disconnected

At least one pair of vertices has no path between them.

Nothing connects 0 or 1 to 2 or 3.

Two separate components.

Kinds of Graphs

Remember: a tree is a connected, acyclic, undirected graph. Every tree is a graph, but not every graph is a tree.

Input vs. Representation

What you are given

edges = [[0, 1], [0, 2], [2, 3]]

A list of pairs is easy to store, but finding the neighbors of one vertex means scanning the whole list.

What you traverse

Convert the input into an adjacency list first. Then every neighbor lookup is instant.

1. Array of Edges

A 2D array where each element is a pair of vertices joined by an edge.

[a, b] means there is an edge from a to b. The problem tells you whether edges are directed.

edges = [[0, 1], [1, 3], [3, 2], [2, 0]]

2. Adjacency List

A hash map from each vertex to a list of its neighbors. It is the most practical format for traversal.

Build it from an array of edges in one pass.

from collections import defaultdict

adj = defaultdict(list)
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)   # skip for directed graphs
# {0: [1, 2], 1: [0, 3], 2: [3, 0], 3: [1, 2]}

3. Adjacency Matrix

An n by n matrix where matrix[i][j] = 1 means there is an edge from i to j.

Checking one edge is O(1), but listing the neighbors of a vertex costs O(n).

4. Grid

A 2D grid where every cell is a vertex. Cells connect to their neighbors above, below, left and right.

The problem defines which moves are allowed, for example only through land cells marked 1.

for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
    r, c = row + dr, col + dc