This lesson includes an expert video walkthrough — purchase once for a full year of unlimited replays to master every key point 🎬
Graph Storage & Definition
Knowledge Summary
Basic Concepts of Graphs
- Graph G = (V, E): V is the set of vertices and E is the set of edges
- Directed graph: edges have direction; (u, v) means an edge from u to v
- Undirected graph: edges have no direction; {u, v} means an edge between u and v
- Weighted graph: edges carry weights such as distance or cost
Basic Terminology
| Term | Definition |
|---|---|
| Degree | Number of edges associated with the vertex |
| In-degree | Number of edges pointing to the vertex in a directed graph |
| Out-degree | Number of edges leaving the vertex in a directed graph |
| Path | A sequence of edges from one vertex to another |
| Cycle | A path whose start and end vertices are the same |
| Simple path | A path that does not pass through repeated vertices |
Important Properties
- In an undirected graph: the sum of all vertex degrees = 2 x number of edges
- In a directed graph: the sum of all in-degrees = the sum of all out-degrees = number of edges
- A complete graph with n vertices has n(n-1)/2 edges if undirected, or n(n-1) edges if directed
Ways to Store Graphs
Adjacency Matrix
int G[N][N]; // G[i][j] = 1 means there is an edge from i to j- Space: O(n²)
- Edge query: O(1)
- Suitable for dense graphs
Adjacency List
vector<int> adj[N]; // adj[i] stores all neighbors of i- Space: O(n + m)
- Suitable for sparse graphs