Sign in to watch this lesson
Algorithms - Graphs I · 3:52
Graph Representations
Before you can search a graph you have to store it, and the layout decides both the memory and the speed. One six-vertex graph goes through an adjacency matrix (36 cells for 7 edges), adjacency lists (each undirected edge stored twice), an edge list and CSR (two flat arrays built by counting sort), with lists and CSR measured on a million vertices on this Mac. Then we meet graphs that are never stored at all: maze cells numbered r * W + c with neighbours from direction arrays, and state graphs whose vertices are (cell, keys) pairs.
You will learn
- Compare adjacency matrix, adjacency lists, edge list and CSR by memory, edge-test cost and neighbour-iteration cost
- Build CSR from an edge list with a counting sort and read a vertex's neighbours from start[] and to[]
- Store undirected and weighted graphs correctly (both directions, wide enough weight types, consistent indexing)
- Treat grids and puzzles as implicit graphs: cell ids r * W + c, direction arrays with bounds checks, and (position, extra state) vertices