Adjacency matrix and adjacency lists
Storing a graph in a machine: adjacency matrix, adjacency lists, edge list, incidence matrix, memory cost and cost of operations, powers of the matrix.
- 23 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
A few cards from the deck
Adjacency matrix: what is it?
Show the answer
An n × n square table whose cell (i, j) is 1 if there is an edge (or arc) from i to j, and 0 otherwise.
It answers “are i and j neighbours?” with one cell read. For a weighted graph the cell holds the weight instead of 1.
What does this program print?
```python
aretes = [("A","B"),("A","C"),("C","B")]
adj = {"A": [], "B": [], "C": []}
for u, v in aretes:
adj[u].append(v)
print(adj)`{'A': ['B', 'C'], 'B': [], 'C': ['B']}{'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B']}{'A': ['B', 'C'], 'B': ['A'], 'C': ['A', 'B']}{'A': ['B', 'C'], 'B': ['C'], 'C': []}
Show the answer
{'A': ['B', 'C'], 'B': [], 'C': ['B']}The code only adds
vtou's list: each pair becomes a directed arc. For an undirected graph it would also needadj[v].append(u); without that line, B keeps no successor.An adjacency matrix takes … cells, whereas adjacency lists take ….
Show the answer
An adjacency matrix takes O(n²) cells, whereas adjacency lists take O(n + m).
The matrix reserves a cell for every possible pair, existing or not; the lists keep only the m real edges.
Adjacency lists: what is it?
Show the answer
A table that associates with each vertex the list of its neighbours (or successors, if the arcs are directed).
It keeps only the links that exist: memory is O(n + m) and a traversal reads each list once.