Quiz — Graph Representations

A road network has 1,000,000 junctions with about 4 roads at each. Which representation suits it, and why?

Hint

Count what each representation stores for this graph, and think about the question a route planner asks most.

An edge list, because it is the smallest

An adjacency list, because it stores about V + E entries where a matrix stores V², 10¹² cells

An adjacency matrix, because checking whether two junctions are joined is O(1)