Exam-style question
Try this first
Compare an adjacency matrix and an adjacency list as ways of representing the same graph. State how each representation records connections and give a situation in which one may be more suitable than the other.
Model answer
What a good answer should say
- An adjacency matrix is a two-dimensional table with a row and column for each vertex.
- The entry at the intersection of two vertices records whether an edge connects them and can record an edge weight where appropriate.
- An adjacency list stores each vertex together with a list of the vertices to which it is connected, and can also store weights with those connections.
- An adjacency matrix gives a direct table-based way to check a particular pair of vertices, but it may contain many entries for pairs that have no edge.
Explanation
Why this works
A strong comparison describes the structure of both representations and links their suitability to the number of connections. It should not claim that either representation is universally best.
Common mistake
No common mistake is linked to this question yet.