Graph Representation

A tree has a strict hierarchy: one root, no cycles, each node with exactly one parent. A graph drops all of those restrictions, it's a more general way to represent connections.

Graph

Real examples: a social network (vertices = people, edges = friendships), a road network (vertices = cities, edges = roads), a web (vertices = pages, edges = links). None of these have a single "root," and cycles (a friend of a friend of a friend being you again) are completely normal.

Terminology

Using the graph above:

• Vertices: A, B, C, D
• Edges: AB, AC, BD, CD
• Path: a sequence of connected vertices, e.g. A → B → D
• Cycle: a path that returns to its starting vertex, e.g. A → B → D → C → A
• Connected graph: every vertex is reachable from every other vertex (in an undirected graph)
• Disconnected graph: at least one vertex (or group of vertices) has no path to another

Directed vs undirected

A social media "follow" is directed (A follows B doesn't mean B follows A); a road connecting two towns is usually undirected (drivable both ways).

Undirected: the edge A — B works both ways, so A can reach B and B can reach A:

Directed, A → B only: the arrowhead shows travel is allowed from A to B, but not from B to A:

Directed, B → A only: the same two vertices, but now the arrowhead points the other way, so only B can reach A:

Directed, both A → B and B → A: two separate edges, drawn as two separate arrows, one each way. This reaches the same result as the single undirected edge shown earlier, A can reach B and B can reach A, but it counts as two distinct edges rather than one.

Weighted graphs

An edge can carry a weight, representing distance, cost, or time:

Weighted graphs matter for problems like shortest-path, covered under graph traversal.

Degree

In the same graph, vertex C is connected to A and D:

So degree(C) = 2, one edge to A and one to D.

In a directed graph, edges pointing in and edges pointing out are counted separately. Take this small directed graph, with vertex D highlighted:

D has one edge pointing in, from B, and three edges pointing out, to A, C, and E. So in-degree(D) = 1 and out-degree(D) = 3.

Adjacency matrix

For the same graph used earlier on this page:

For an undirected graph the matrix is symmetric, matrix[i][j] == matrix[j][i], since an edge works both ways. For a directed graph it generally isn't: rows represent source vertices, columns represent destinations.

Directed example: A → B, A → C, C → B

Adjacency list

When vertices have very different degrees, the matrix and the list diverge in how much space they use. Take this directed graph with five vertices, where out-degrees range from 0 to 3:

Now the difference is obvious. Vertex D has three outgoing edges, so its matrix row has three 1s and its list has three neighbors, both correctly reflect that D is the "busiest" vertex. Vertex E has none: its matrix row is all 0s (five wasted cells), while its list is simply empty (an X right at the header, no wasted space at all). This unevenness is exactly what makes the space row in the comparison table below matter in practice, a matrix pays the same V cells per row no matter how few edges that vertex actually has, while a list pays only for edges that exist.

This graph is directed and not symmetric: A → B exists but B → A does not, so matrix[A][B] = 1 while matrix[B][A] = 0. An undirected graph's matrix is always symmetric; a directed one usually isn't.

Matrix vs list

Feature	Adjacency matrix	Adjacency list
Space	O(V²)	O(V + E)
Check if edge (i, j) exists	O(1)	Usually O(degree of i)
Dense graph (many edges)	Good	Less ideal
Sparse graph (few edges)	Wastes space	Good
Finding all neighbors of v	Scan a full row	Already a direct list

The matrix reserves a slot for every possible pair of vertices, whether an edge exists or not, O(V²) regardless of how many edges actually exist. The list stores only the neighbors that actually exist, O(V + E), so it scales much better for sparse graphs (most real-world graphs, like social networks or road maps, are sparse).

Quick recall

• G = (V, E): a set of vertices and a set of edges, no root, cycles allowed, may be disconnected.
• Directed edges are one-way (A → B ≠ B → A); undirected edges work both ways.
• Degree: edges incident on a vertex (undirected); in-degree/out-degree separately for directed graphs.
• Adjacency matrix: V × V table, O(1) edge lookup, O(V²) space, best for dense graphs.
• Adjacency list: per-vertex neighbor lists, O(V+E) space, best for sparse graphs, the more common real-world choice.