Data structures · 2 lessons
Graph RepresentationStoring a graph, and answering "connected?"
A graph is nodes and edges, and it can describe any problem about things being related. This topic is only about storage: when to use an adjacency list versus a matrix, and union-find, a structure built specifically for connectivity. The algorithms live under Graph Algorithms.
Why learn Graph Representation
Where it shows upFriendships in a social network
A billion users with a few hundred friends each. An adjacency matrix would need 10¹⁸ cells; an adjacency list stores only the edges that exist.
→ Lesson: Adjacency List / MatrixIs the network still connected?
Links between data centres come and go, and you need "can A still reach B?" at any moment. Union-find makes that almost constant time.
→ Lesson: Union-FindGrouping faces in a photo library
Draw an edge between two similar faces, and each connected component ends up being one person. Union-find is the simplest clustering tool there is.
→ Lesson: Union-FindLessons
2 lessons#AlgorithmComplexityDifficultyStatus
01Adjacency List / Matrix Adjacency lists and matricesDirected, undirected, weighted; the sparse versus dense trade-offUsed for: The input format for every graph algorithmO(V+E) / O(V²)Space O(V+E) / O(V²)available02Union-Find Union-findPath compression, union by rankUsed for: Connectivity checks, clustering, the core of KruskalO(α(n))Space O(n)available