#datastructure#graph

An adjacency matrix is a square matrix, used to represent a finite graph. Each element indicate whether pairs of vertices are connected or not.

For weighted graph, the matrix's element could be some number other than 1.

The drawbacks of using adjacency matrix is memory. No matter how many edges are there, we always need $N \times N$ sized matrix, where $N$ is the number of nodes.

If there are 10000 nodes, then the matrix size will be $4 \times 10000 \times 10000$, that's around 381MB, a huge waste of memory if the graph only have a few edges.

Another point is, if we want to find out which node we can go from a node $u$, we'll need to check the whole row of $u$, which cost a lot of time.

See also: §202109142250 Represent Graph using Adjacency List