P-4.7 Graphs, and How to Store Them

Work through these

• Vertices and edges, directed and undirected, weighted and unweighted

  The vocabulary is small and the modelling decisions are where the thinking happens. Whether an edge has a direction and whether it carries a cost change which algorithms apply.

• Recognising a graph problem that does not look like one

  Dependencies between tasks, moves in a puzzle, and conversions between currencies are all vertices and edges. Naming the vertices and the edges is usually the hardest step and the one that solves the problem.

  Algorithms · Reference

• The adjacency matrix: constant-time edge tests, quadratic memory

  A grid of every vertex against every other answers is there an edge immediately. For a sparse graph with thousands of vertices it also wastes an enormous amount of memory.

• Adjacency lists: memory proportional to the edges that exist

  Storing each vertex with the vertices it connects to costs only what the graph actually contains. Testing one specific edge is slower, and most algorithms iterate over neighbours anyway.

• Choose a representation for a real graph and defend the choice

  Take something concrete like a road network or a dependency listing, estimate the vertex and edge counts, and pick. Being able to say why is the outcome here, not the pick itself.