Graph Representations
A graph can be stored as an adjacency matrix or an adjacency list; the choice trades memory against the cost of listing a vertex's neighbours.
Vertices and edges
A graph is a set of vertices connected by edges. Edges may be directed or undirected and may carry weights. Almost every graph algorithm needs to answer two questions efficiently: is there an edge between u and v, and what are the neighbours of v? The two standard representations answer these differently.
Adjacency matrix
An adjacency matrix is a V-by-V grid where entry (u,v) records whether, or how heavily, u connects to v. Edge existence is an O(1) lookup, which is ideal for dense graphs and algorithms like Floyd-Warshall. The cost is O(V^2) space regardless of how few edges exist, and listing a vertex's neighbours takes O(V) because you scan a whole row.
Adjacency list
An adjacency list keeps, for each vertex, a list of its neighbours. Space is O(V + E), proportional to the actual edges, so it is far leaner for sparse graphs. Listing neighbours is optimal, but checking whether a specific edge exists takes time proportional to the vertex's degree. Most traversal algorithms, including BFS and DFS, prefer this form.
- Matrix: O(V^2) space, O(1) edge test, O(V) to list neighbours
- List: O(V+E) space, O(degree) edge test, O(degree) to list neighbours
- Dense graphs favour the matrix; sparse graphs favour the list
Choosing
Real-world graphs, from road networks to social networks, are usually sparse, so adjacency lists dominate practice. Reach for a matrix when the graph is dense, when you test individual edges constantly, or when an algorithm is naturally expressed as matrix operations.