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

Taught in

References