Graph representation by Adjacency Matrix— a quick review
Graphs can be represented in multiple ways. Each has its pro’s and con’s. Each representation has tradeoffs. Updated Dec 3, 2020
Adjacency Matrix
A B C D
A 0 1 1 1
B 1 0 0 0
C 1 0 0 1
D 1 0 1 0# A is adjacent to B, C, D
# C is adjacent to A, D
It’s easy to see which nodes are connected, and how many degrees of connection each node has (sum across rows or sum across columns). Easy to spot loops — if a node is connected with itself and the diagonal will have one or more 1's. If there’s no loop, the diagonal will be all zeroes.
# connected?
if grid[i][j] == 1It’s useful for finding neighbors as well. But when the number of nodes increase, this matrix can get very sparse (lots of zeroes), and can become wasteful in terms of space. Watch out for double counting connections in undirected graphs when (A,B) and (B,A) are equivalent. It’s possible to only use the upper triangle above the matrix diagonal only during analysis.
Adjacency List Real World Example
follow = {
"kathleen" : ["anna", "alice"],
"john" : ["lee", "david"],
"alice" : ["anna"]
}note the above list looks more like a follower adjacency list, not a symmetric friend. For example kathleen follows anna and alice, but alice only follows anna not kathleen.
