Graphs are fundamental data structures modeling relationships between entities — consisting of vertices (nodes) connected by edges. They appear throughout computer science, from social networks and routing algorithms to dependency analysis and fraud detection. Graphs can be directed or undirected, weighted or unweighted, cyclic or acyclic — each variant enabling different algorithmic approaches. A key insight: the choice between adjacency list and adjacency matrix representation profoundly impacts both memory usage and traversal speed — sparse graphs favor lists ($O(V + E)$ space), while dense graphs benefit from matrices' $O(1)$ edge lookups at the cost of $O(V^2)$ space. Modern graph data science extends classical algorithms with centrality measures, community detection, and node embeddings that unlock insights in large-scale networks.
What This Cheat Sheet Covers
This topic spans 17 focused tables and 95 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
A jump-to index of every table row in this cheat sheet.
An interactive map of every table and concept in this topic.
Table 1: Graph Representations
Every graph algorithm starts with a choice about how to store the graph in memory, and that choice quietly shapes its speed and footprint. Adjacency lists win for sparse graphs and traversal, adjacency matrices give you instant edge lookups on dense graphs, and edge lists, CSR, and incidence matrices each suit a narrower job — from sorting edges for Kruskal's to packing huge graphs onto a GPU.
| Type | Example | Description |
|---|---|---|
graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]} | • Dictionary or array mapping each vertex to its neighbor list • space-efficient for sparse graphs — $O(V + E)$ space, ideal for traversal algorithms. | |
matrix = [[0, 1, 1, 0], [0, 0, 1, 0], [1, 0, 0, 1], [0, 0, 0, 1]] | • 2D array where matrix[i][j] = 1 if edge $i \to j$ exists• $O(V^2)$ space, $O(1)$ edge lookup, best for dense graphs or matrix operations. | |
edges = [(0,1), (0,2), (1,2), (2,3)] | • Simple list of edge tuples (or triples with weights) • $O(E)$ space, useful for sorting edges (Kruskal's MST) but slow for neighbor queries. |