What's the difference between an adjacency matrix and an adjacency list in graph representation?

An adjacency matrix is a square matrix used to represent a finite graph, while an adjacency list is a collection of unordered lists used for the same purpose.

An adjacency matrix is a 2D array of size V x V where V is the number of vertices in a graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. Each node has a list that represents the nodes that it is connected to. The size of the matrix is V^2, making it a good choice if the graph is dense, i.e., the number of edges is close to the number of vertices squared. This dense representation is similar to how data is structured in databases, which you can explore further here.

On the other hand, an adjacency list is a collection of separate lists. Each list describes the set of neighbours of a vertex in the graph. This is the more space-efficient way to implement a sparsely connected graph, i.e., a graph in which the number of edges is far less than the number of vertices squared. In an adjacency list, each vertex has its own list that contains the vertices it is connected to. The size of the list is 2E, where E is the number of edges.

In terms of time complexity, for operations like looking up if edge (u, v) is in the graph, an adjacency matrix takes O(1) time, while an adjacency list takes O(V) time, where V is the number of vertices. However, for operations like iterating over the edges, an adjacency matrix takes O(V^2) time, while an adjacency list takes O(V + E) time. The structure and management of these graph representations can often be visualised in a web graph representation, a concept detailed here.

A-Level Computer Science Tutor Summary: An adjacency matrix uses a 2D array to show connections between nodes, making it good for dense graphs. An adjacency list uses separate lists for each node's neighbours, saving space in sparse graphs. Matrices are fast for checking connections, while lists are better for looping through edges. Choose based on your graph's density and your needs.