adjacency matrix
A graph representation as a V-by-V grid in which the cell at row i, column j records whether, or with what weight, an edge runs from vertex i to vertex j.
In more detail
Checking for a specific edge is O(1), but the grid takes O(V^2) memory however few edges exist, and listing a vertex's neighbours means scanning a whole row. It pays off for dense graphs where most pairs are connected.
Related terms
- adjacency list — A graph representation that stores, for each vertex, a list of its neighbours, typically as a dict of lists in Python.
- dense graph — A graph in which most pairs of vertices are connected, so the edge count is close to V squared.
- graph — A set of vertices (points) connected by edges (links), used to model networks such as roads, friendships or dependencies.
Taught in
- Representing A Graph: Matrix Or Adjacency List — Algorithms & Data Structures for Working Engineers