The diagram shows a weighted, undirected graph.
(a) The graph is to be stored as an adjacency matrix. Complete rows C, D and E of the matrix, using 0 where there is no edge. [2]
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 4 | 2 | 0 | 0 |
| B | 4 | 0 | 5 | 10 | 0 |
| C | |||||
| D | |||||
| E |
(b) Explain why an adjacency list might be more suitable than an adjacency matrix for storing a graph with many vertices but few edges. [2]
(c) Explain why this graph is not a tree. [1]
- (a) Row C correct: 2, 5, 0, 0, 3(1)
- (a) Rows D and E correct: D = 0, 10, 0, 0, 4; E = 0, 0, 3, 4, 0(1)
- (b) A matrix stores an entry for every possible pair of vertices (n² entries), most of which would be empty/0 for a sparse graph, wasting memory(1)
- (b) An adjacency list only stores the edges that exist, so it uses less memory (the time to check a specific edge being slower is acceptable)(1)
- (c) It contains a cycle (e.g. A–B–C–A); a tree is a connected graph with no cycles(1)
- Answer: (a) C: 2 5 0 0 3; D: 0 10 0 0 4; E: 0 0 3 4 0 (b) Sparse graph – matrix wastes memory on n² mostly empty entries; list stores only existing edges. (c) It has a cycle, e.g. A–B–C–A.
- Examiner tip: An undirected graph's matrix is symmetric – use that to check your rows.