Data Structures
Graphs: Connections Between Everything
Цели урока
- Understand what a graph is and where it is used
- Learn the terminology: vertex, edge, degree, path
- Distinguish graph types: directed/undirected, weighted
- Master the two representations: adjacency list and adjacency matrix
Предварительные знания
- Hash tables
The Seven Bridges of Konigsberg
In 1736 Leonhard Euler asked whether one could cross all seven bridges of Konigsberg exactly once and return home. He abstracted the city into land masses as vertices and bridges as edges, proved no such walk exists, and in doing so founded graph theory. The two standard storage forms, the adjacency matrix and the adjacency list, were formalized as the field matured, and Frank Harary's 1969 book Graph Theory consolidated the vocabulary of vertices, edges, and degree that the discipline still uses.
Google Maps, Facebook's friend recommendations, package manager dependency resolution, Git history - all of these are graphs. Mastering graphs means understanding the data structure behind the most influential software systems in the world.
- Google PageRank: the web is a directed graph; PageRank counts incoming edges to determine page importance
- Social networks: shortest path between users is a BFS problem (six degrees of separation)
- GPS navigation: shortest route is Dijkstra's algorithm on a weighted graph
Graphs Are Everywhere
A **graph** is a set of objects (**vertices**) and the connections between them (**edges**). Anywhere objects relate to one another, a graph is hiding underneath.
- **The web** - pages and hyperlinks
- **Social networks** - users and friendships
- **Maps** - cities and roads
- **Dependencies** - npm packages and their imports
- **Biology** - proteins and their interactions
Which of the following is NOT a graph?
Graph Terminology
- **Vertex** - a node of the graph
- **Edge** - a connection between two vertices
- **Adjacent** - two vertices joined by an edge
- **Degree** - the number of edges at a vertex
- **Path** - a sequence of vertices linked by edges
- **Cycle** - a path that starts and ends at the same vertex
Graph: A-B, A-C, A-D, B-C. What is the degree of vertex A?
Types of Graphs
Directed vs Undirected
Weighted vs Unweighted
Other types
- **DAG** - Directed Acyclic Graph (no cycles)
- **Tree** - a connected graph with no cycles
- **Bipartite** - vertices split into two groups, edges only between groups
Twitter (follows) is a graph that is:
Representation: Adjacency List
An **adjacency list** stores, for each vertex, the list of its neighbors.
| Metric | Adjacency List |
|---|---|
| Memory | O(V + E) |
| Check edge | O(degree) |
| All neighbors | O(degree) |
| Add edge | O(1) |
The best choice for sparse graphs, where edges are few relative to vertices.
An adjacency list is optimal for:
Representation: Adjacency Matrix
An **adjacency matrix** is a V x V table where matrix[i][j] = 1 when an edge exists.
| Metric | Adjacency Matrix |
|---|---|
| Memory | O(V^2) |
| Check edge | O(1) |
| All neighbors | O(V) |
| Add edge | O(1) |
A matrix suits dense graphs, or any case where fast edge checks are the priority.
An adjacency matrix guarantees faster neighbour enumeration thanks to O(1) edge checks.
Listing the neighbours of a vertex via a matrix requires scanning a full row in O(V). An adjacency list returns them in O(degree), which on a sparse graph is orders of magnitude faster.
O(1) for a single edge check looks like an absolute win, and 'V checks of O(1)' sounds equivalent to walking a list. On sparse graphs degree is much smaller than V, so the list yields the actual neighbours directly without wasting time on empty matrix cells.
When is an adjacency matrix better than a list?
Graph representations
- A graph = vertices + edges; models relationships between objects
- Directed/Undirected, Weighted/Unweighted
- Adjacency list: O(V+E) memory, for sparse graphs
- Adjacency matrix: O(V^2) memory, O(1) edge lookup, for dense graphs
Вопросы для размышления
- Graphs are an abstraction over relationships. Which business or everyday problems hide a graph that nobody names as such, and how does reframing them in vertices-and-edges language change the solution?
- A billion-user social network rules out an adjacency matrix (10^18 cells). Which three or four signals in a problem statement should instantly drop the matrix and leave only adjacency lists or specialized representations (CSR, edge list)?
- A DAG enables topological sort and fast DP. Which real systems (git, build tools, neural nets) rely specifically on the acyclic property, and what would break first if a cycle slipped in?
Connections to other topics
Graphs are the foundation for a whole family of algorithms
- Union-Find — Efficient data structure for connected components in a graph
- Dijkstra / Shortest Paths — BFS extension for weighted graphs
- Topological Sort — DFS application for DAGs and dependency ordering
Связанные уроки
- ds-14-heaps-intro — Priority queue needed for graph traversal (Dijkstra)
- ds-17-graph-algorithms — BFS/DFS/Dijkstra are built on top of graph structure
- sd-18-consistent-hashing — Consistent hashing is a graph on a ring of nodes
- net-02-osi-overview — IP network is a weighted graph of routers
- comp-22-ssa