Advanced · Module 13 · Lesson 1 of 5
Representing graphs
A graph is a set of vertices joined by edges. How you store it, as adjacency lists, an adjacency matrix or an edge list, decides the cost of every algorithm you run on it.
By the end you can
- Use graph vocabulary: directed and undirected, weighted, degree, sparse and dense
- Build an adjacency list from an edge list, and compare it with a matrix and an edge list
- Recognize implicit graphs, such as grids and puzzle states, whose edges are computed on demand
Builds on Level-order traversal.
01 · A question first
A road map, a social network, course prerequisites and a maze are all graphs. A social network of a billion people, each with a few hundred friends, would need a billion billion cells as a matrix, but only a few hundred billion entries as lists. How do you choose a representation?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Graphs everywhere
- Three representations
- Practical variations
- Choosing in practice
- Implicit graphs
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem