Graph Representation

Before you can traverse or search a graph, you need to represent it in code. There are two main approaches: adjacency list and adjacency matrix.

Each vertex stores a list of its neighbors. This is the most common representation and is space-efficient for sparse graphs.

A 2D array where matrix[i][j] indicates if an edge exists between vertices i and j. Good for dense graphs or when you need O(1) edge lookups.

2D grids are implicit graphs. Each cell is a vertex, and adjacent cells are neighbors.

Adjacency List: Most interview problems, sparse graphs, when you need to iterate over neighbors
Adjacency Matrix: Dense graphs, when you need O(1) edge lookups, Floyd-Warshall algorithm
Grid: Maze problems, flood fill, island counting

Was this helpful?

Adjacency List