How do you represent a graph with an adjacency list and with an adjacency matrix?
An adjacency list is a dictionary that says, for each node, which nodes it is joined to. An adjacency matrix is a table where the row is one node and the column is another, and the cell says whether they are joined.
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A"],
"D": ["B"],
}
And here is the same graph as a matrix. The rows are the nodes and the columns are the nodes, and a one means that there is an edge.
A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 0
D 0 1 0 0
And the two of them have very different costs, and the choice comes down to how many edges there are.
the thing the adjacency list the adjacency matrix
------------------ ------------------ -------------------
the space O(n + m) O(n^2)
is there an edge? O(degree of node) O(1)
the neighbours O(degree of node) O(n)
a dense graph worse better
a sparse graph better worse
So where n is the number of nodes and m is the number of edges. The list only stores the edges that exist, so a sparse graph is cheap. The matrix always stores n squared cells, so a sparse graph wastes a lot of space, but then the check for one edge is instant.
And the adjacency list is what you use almost always in an interview, because most real graphs are sparse. The matrix is worth knowing about for the dense case and for the algorithms that use it, such as the Floyd Warshall shortest path algorithm.
And there is a detail worth knowing about. In an undirected graph the matrix has to be symmetric, because if A is joined to B then B is joined to A. And the list has the same rule, so the neighbours of A include B and the neighbours of B include A.
So the rule to remember is this. The list is for sparse graphs and the matrix is for dense ones.
The next two questions in this topic show the edge check and the counting.