DataslopeGraphs
Learn graph vocabulary, representations, density, degrees, and C++ graph construction patterns
A graph is a collection of vertices V and edges E. Vertices are the objects; edges are relationships between them. Graphs are the language of networks: social follows, road maps, web links, package dependencies, neural network topology, game maps, and workflow pipelines.
Graph vocabulary
- Undirected graph: an edge
{u, v}works both ways. - Directed graph: an edge
(u, v)goes fromutov. - Weighted graph: each edge carries a cost, distance, latency, or capacity.
- Unweighted graph: every edge is treated equally.
- Cyclic graph: at least one path loops back to a vertex.
- Acyclic graph: no cycles. A directed acyclic graph is called a DAG.
This is a small undirected graph. Edge 0-1 also means 1-0.
This is a directed weighted graph. The arrow and weight both matter.
Graphs generalize many structures
A linked list is a graph where each vertex has at most one outgoing edge. A tree is a connected acyclic graph. Once you learn graph thinking, many data structures become special cases.
The same example in three representations
Use vertices 0, 1, 2, 3 and undirected edges 0-1, 0-2, 1-2, 2-3.
Adjacency matrix
An adjacency matrix is a V × V table. matrix[u][v] tells whether edge u -> v exists. It uses O(V²) space and supports O(1) edge lookup.
Matrix lookup is great for dense graphs or repeated hasEdge(u, v) checks.
Adjacency list
An adjacency list stores only existing neighbors. It uses O(V + E) space, so it is usually best for sparse graphs.
For a weighted graph, store (neighbor, weight) pairs.
Edge list
An edge list stores edges directly. For weighted graphs, use vector<tuple<int,int,int>> as (u, v, w). Edge lists are simple and especially useful for Kruskal's algorithm.
Degrees and neighbors
In an undirected graph, the degree of a vertex is its number of incident edges. In a directed graph, out-degree counts outgoing edges and in-degree counts incoming edges.
A graph is sparse when E is much smaller than V². It is dense when the possible edges are mostly present. Sparse graphs usually prefer adjacency lists; dense graphs can justify matrices.
Challenge: Count edges in an undirected graph from adjacency list
Implement countEdges. In an undirected adjacency list, each edge appears twice, so sum all degrees and divide by 2.
Challenge: Convert adjacency list to adjacency matrix
Implement toMatrix so every listed edge u -> v becomes a 1 in the returned matrix. The driver prints each row with spaces between values.
Check your understanding
You are storing a graph with one million vertices and only a few million edges. Which representation is usually best?
Adjacency matrix
Adjacency list
A sorted array of vertices only
A single stack
What is a DAG?
A graph where every edge has the same weight
A dense adjacency graph
A directed acyclic graph
A graph represented only by a matrix
How does edge lookup hasEdge(u, v) compare between an adjacency matrix and an unsorted adjacency list?
Matrix is O(1); list is O(degree(u))
Matrix is O(V²); list is O(1)
Both are always O(1)
Both are always O(E)