Graphs and How to Store Them · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Storing maps as matrices or lists

Computing · Algorithms & Data Structures · ages 17-18
Name ______________________   Date ____________

  1. A route map shows a road from Ashcombe to Bridgeton that is 5 km long, and a road from Bridgeton to Cliffwood that is 8 km long. If we model this map as a graph, what do the numbers 5 and 8 represent?

    • Edge weights
    • Node names
    • The number of nodes
    • The number of edges

  2. A directed graph has nodes A, B, C, D. The edges are A→B, A→C, B→D, and C→D. In an adjacency matrix with rows and columns ordered A, B, C, D, which row correctly shows node A's connections (0 = no edge, 1 = edge)?

    • 0, 1, 1, 0
    • 1, 0, 1, 1
    • 0, 0, 0, 1
    • 1, 1, 0, 0

  3. A dense graph has 6 nodes, and its adjacency matrix has one row and one column for every node. How many cells does the full matrix have?

    Answer: ______________

  4. For that same graph, what does the adjacency list entry for A look like?

    • A: B, D
    • A: B, C
    • A: C, D

  5. Most pairs of nodes in a graph are directly joined. Which store is usually more compact?

    • Adjacency list
    • Adjacency matrix
    • A plain towns list

  6. A graph's adjacency list is written as: A: B, C / B: C / C: (nothing). How many directed edges does this graph have in total?

    Answer: ______________

  7. In a dense graph, where most possible pairs of nodes are actually connected, true or false: an adjacency matrix usually wastes less space than an adjacency list.

    Circle one:   True   False

  8. A friendship graph has 10,000 people, and each person is friends with about 20 others on average. Which storage format uses less memory for this graph?

    • Adjacency list
    • Adjacency matrix

  9. A list reads A: B, C with B: C and C: none. How many directed edges in total?

    Answer: ______________

  10. Roads Ashcombe to Bridgeton 5 km and Bridgeton to Cliffwood 8 km join the map. What are 5 and 8?

    • Node names
    • Edge counts
    • Edge weights
LightMySky · lightmysky.comW1-mt_tSO-F1sTuu-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Storing maps as matrices or lists W1-mt_tSO-F1sTuu-s1

  1. Edge weights · A weight is a number attached to an edge. Here, the distances 5 km and 8 km are attached to the road edges, so they are the edge weights.
  2. 0, 1, 1, 0 · Row A marks a 1 wherever A has an outgoing edge. A points to B and to C, so the row reads 0 (to A), 1 (to B), 1 (to C), 0 (to D).
  3. 36 · A matrix for n nodes always has n rows and n columns, so it has n times n cells.
  4. A: B, C · A list names only the direct outgoing neighbours.
  5. Adjacency matrix · Dense graphs fill nearly every matrix cell with real links.
  6. 3 · Each name listed after a node's colon is one directed edge starting at that node. Add up all the names across every node.
  7. True · When most pairs are connected, a list has to store almost as many neighbor entries as a matrix has cells anyway, plus extra pointers. The matrix's flat grid of 0s and 1s ends up more compact for dense graphs.
  8. Adjacency list · With only about 20 friends per person out of 10,000 possible, almost every matrix cell would be empty. A list only stores the real friendships, so it takes much less space.
  9. 3 · Each named neighbour is one directed edge.
  10. Edge weights · Numbers attached to edges are weights, here distances.
Worksheet · LightMySky