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.
Table 1: Graph Representations
| 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. |