A graph is a data structure made up of vertices (also called nodes) connected by edges. Where a tree forces a strict hierarchy — one parent per node, no cycles — a graph has no such restriction. Any vertex can connect to any number of other vertices, in any pattern, including cycles that loop back on themselves. That flexibility makes graphs the right model for things that don't naturally form a hierarchy: social networks, road maps, flight routes, dependency chains, and the web itself are all graphs at heart.

In fact, a tree is really just a special, restricted case of a graph — one with no cycles and exactly one path between any two nodes.

Key Terminology

A few terms come up constantly when working with graphs:

Directed vs undirected — in a directed graph, an edge has a direction (A → B doesn't imply B → A), like a one-way street or a "follows" relationship on social media. In an undirected graph, edges go both ways equally, like a friendship or a road connecting two towns.

Weighted vs unweighted — a weighted graph attaches a cost or distance to each edge (useful for things like road distances or flight prices), while an unweighted graph treats every edge as equal.

Adjacent / neighbor — two vertices connected directly by an edge. Path — a sequence of edges connecting one vertex to another. Cycle — a path that starts and ends at the same vertex.

Representation 1: Adjacency List

An adjacency list stores, for each vertex, a list of the vertices it connects to directly — typically as a dictionary mapping each node to its neighbors. This is by far the most common representation in practice.

# An undirected graph as an adjacency list
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"]
}

print(graph["D"])   # everything D is directly connected to

Output:

['B', 'C', 'E']

Space usage is O(V + E) — proportional to the number of vertices plus edges — which is efficient for sparse graphs, where most vertices only connect to a few others. This is the representation used throughout the BFS and DFS tutorials.

Representation 2: Adjacency Matrix

An adjacency matrix uses a 2D grid where matrix[i][j] is 1 (or a weight) if an edge exists between vertex i and vertex j, and 0 otherwise.

# Same graph as a matrix (A=0, B=1, C=2, D=3, E=4)
#      A  B  C  D  E
matrix = [
    [0, 1, 1, 0, 0],  # A
    [1, 0, 0, 1, 0],  # B
    [1, 0, 0, 1, 0],  # C
    [0, 1, 1, 0, 1],  # D
    [0, 0, 0, 1, 0],  # E
]

# Checking if B and D are connected is O(1):
print(matrix[1][3])

Output:

1

Which Representation Should You Use?

An adjacency matrix gives O(1) edge lookups ("are these two vertices connected?") but always uses O(V²) space, even if the graph barely has any edges — wasteful for sparse, real-world graphs like a social network. An adjacency list uses only O(V + E) space and is faster to iterate over a vertex's neighbors, but checking whether two specific vertices are connected takes O(degree) instead of O(1).

In practice, adjacency lists win for almost all real-world graphs, since most graphs you'll actually work with are sparse — each vertex connects to a small fraction of the total, not everything. Matrices mainly earn their keep on small, dense graphs or when O(1) edge lookups matter more than memory.