Search code examples
data-structuresgraph-theoryadjacency-matrixadjacency-list

Difference between adjacency list and adjacency matrix

I often see my tutor referencing to both adjacency lists and adjacency matrix in Graph theory
But I still don't understand the difference?
Any help please?

Solution

  • Adjacency list shows which nodes are connected to which, in the following format:

    2 3 4 5
1 4
1 5 4
1 2 5 3
1 3 4

    This means node 1 is connected to nodes 2, 3, 4 and 5, node 2 is connected to 1 and 4, and so on.

    The adjacency matrix, on the other hand, does it in the following matrix format:

    01111
10010
10011
11101
10110

    It shows that if the 1st node and 2nd node are connected, there is a 1 at the grid[1][2] position, and 0 if the 2 nodes aren't connected, or if they are the same nodes. Hope this helps!