Micro-questions over the graph representations module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
Reference graph throughout: edges A-B, A-C, B-C, B-D, C-D.
A. Edge list
1. What is an edge list?
Answer
Just the edges, as pairs: [("A","B"), ("A","C"), ("B","C"), ("B","D"), ("C","D")].
2. What space does it use?
Answer
— the smallest of the five.
3. What is it good at?
Answer
Iterating every edge, in — exactly what Kruskal’s algorithm wants, since it sorts all edges by weight.
4. What is it bad at?
Answer
Finding one vertex’s neighbours — you must scan everything, .
B. Adjacency list
5. What is an adjacency list?
Answer
For each vertex, the list of its neighbours: {"A": ["B","C"], "B": ["A","C","D"], ...}.
6. Space, and cost of neighbours(v)?
Answer
Space ; neighbours in — optimal, you touch exactly what you need.
7. Cost of checking one specific edge?
Answer
— you scan the list.
8. Why is this the default?
Answer
Because BFS, DFS, Dijkstra and topological sort all iterate neighbours and never ask about a random pair.
C. Adjacency map
9. What is an adjacency map?
Answer
The same idea as an adjacency list, but each neighbour collection is a hash map or set rather than a list: {"A": {"B": 1, "C": 1}, ...}.
10. What does it gain?
Answer
Edge lookup and edge deletion become average instead of , and edge weights get a natural home.
11. What does it cost?
Answer
Still space, but with a larger constant — hash sets are heavier than plain lists.
12. When is it the right default?
Answer
For a graph that changes. It is what NetworkX uses.
D. Adjacency matrix
13. What is an adjacency matrix?
Answer
A grid with when the edge exists.
14. What space does it use, and what is the crucial qualifier?
Answer
— regardless of edge count. An empty graph costs the same as a complete one.
15. Cost of edge lookup and of listing neighbours?
Answer
Edge lookup: a genuine array index. Neighbours: — you scan a whole row even if the vertex has two neighbours.
16. What is true of the matrix for an undirected graph?
Answer
It is symmetric, and the diagonal is non-zero exactly where self-loops are.
17. What is its real algebraic payoff?
Answer
counts the walks of length from to .
18. Why walks and not paths?
Answer
Matrix multiplication sums over all intermediate sequences, including ones that revisit vertices. Counting paths is a much harder problem.
E. Incidence matrix
19. What is an incidence matrix?
Answer
A grid — rows are vertices, columns are edges, and an entry marks that the vertex is an endpoint of that edge.
20. What space does it use?
Answer
— the largest of all, and rarely used for computation.
21. What are its two genuine uses?
Answer
- It handles parallel edges naturally, where an adjacency matrix cannot distinguish them.
- For directed graphs, with for the tail and for the head, it is the matrix whose null space is the cycle space — the foundation of network-flow and electrical-circuit formulations.
22. What does each column sum to in the undirected case, and why?
Answer
2 — because every edge has two endpoints. That is the handshake lemma again.
F. Choosing one
23. Give the space of all five.
Answer
Edge list ; adjacency list ; adjacency map ; adjacency matrix ; incidence matrix .
24. Cost of adjacent(u,v) in each?
Answer
Edge list ; adjacency list ; adjacency map ; adjacency matrix ; incidence matrix .
25. Cost of neighbours(u) in each?
Answer
Edge list ; adjacency list ; adjacency map ; adjacency matrix ; incidence matrix .
26. Read those two rows together — what is the single trade?
Answer
The adjacency matrix wins adjacent and loses neighbours; the adjacency list does the opposite. That trade is what choosing a representation means — which is why “which is best?” has no answer until you know which operation your algorithm calls most.
27. Cost of remove_edge in edge list vs adjacency map?
Answer
Edge list — find it first. Adjacency map average.
28. Give the five practical decisions.
Answer
- Sparse () and you traverse → adjacency list (most real graphs).
- The graph changes, or you need edge lookup → adjacency map.
- Dense (), small , or matrix algebra → adjacency matrix.
- Sorting edges (Kruskal) or a file format → edge list.
- Parallel edges, or the cycle space → incidence matrix.
29. Where is the crossover between list and matrix?
Answer
Roughly if you store matrix bits — or simply where stops fitting in memory.
30. Why is a matrix not an option at , at any density?
Answer
entries. Even one bit each is 125 GB.
31. A social network has users averaging 200 friends. Compare list and matrix storage.
Answer
Adjacency list: entries. Adjacency matrix: entries. About 5,000× more for the matrix — and the matrix is 99.98% zeros.
G. Implicit graphs
32. What is an implicit graph?
Answer
One you never store at all — the neighbours are computed on demand rather than looked up.
33. Give the grid-maze example.
Answer
Each cell is a vertex and each open orthogonal neighbour is an edge. You generate neighbours by adding the four offsets and bounds-checking, instead of building any adjacency structure.
34. Where else does this apply?
Answer
State-space search — puzzle configurations, word ladders, game positions — where the graph is astronomically large but each node’s neighbours are cheap to generate.
35. State the idea in one sentence.
Answer
You traverse the graph without ever holding it.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Graph Representations — the module
- What a Graph Is — Question Bank — where the ADT is defined
- Graph Traversal — the algorithms that consume
neighbours()
Software engineering
Infrastructure & security
Computer science
Hardware & engineering