Pro

The 4 Graph Input Formats You Need to Recognize

Graph problems rarely say "here is a graph". They describe it in one of four formats, and spotting the format quickly tells you how to build your traversal.

Below is each format with the same idea drawn as a picture.

1) Edge List

You receive a list of pairs, where each pair names two vertices joined by an edge. The problem statement says whether an edge [a, b] goes one way or both ways. Build an adjacency list from it before traversing.

1. Edge List

The input is a 2D array, and each inner pair is one edge between two vertices.

[a, b] means an edge runs from a to b.

The problem tells you whether edges are directed or undirected.

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

2) Adjacency List

The most convenient format. Each vertex maps straight to the vertices it connects to, so you can loop over neighbors right away. In Python this is usually a dictionary of lists.

2. Adjacency List

Each vertex points to the list of vertices it is directly connected to.

A hash map works well: the key is a vertex and the value is its neighbor list.

You often build one yourself from an edge list.

"P": ["Q"], "Q": ["R", "T"], "R": [], "S": ["R"], "T": []

3) Adjacency Matrix

An n by n grid of 0s and 1s, where row i and column j say whether vertex i has an edge to vertex j. Checking a single edge is instant, but listing neighbors means scanning a whole row.

3. Adjacency Matrix

The input is an n x n matrix of 0s and 1s.

matrix[i][j] == 1 means there is an edge from vertex i to vertex j.

You can turn it into an adjacency list first, but you do not have to.

Edges:

0 → 1 1 → 2 1 → 3 2 → 0

4) Grid

Each cell of a 2D grid is a vertex, and the problem describes which neighboring cells you may move to. Classic examples count islands of land cells or spread something through the grid one step at a time.

4. Grid

The input is a 2D matrix and every cell is a vertex.

The problem defines the edges, for example "you may step onto an adjacent 1 above, below, left or right".

✔ Reachable from the top left corner