Adjacency Matrix

overview

Summary

An adjacency_matrix is a square n×n matrix that represents a graph with n vertices. Entry A[i][j] indicates whether an edge exists from i to j, or stores the edge weight in weighted graphs. It offers O(1) edge existence checks and O(1) edge updates, but uses O(n^2) space and O(n) time to list neighbors. It shines for dense or small graphs and for algorithms that benefit from matrix operations.