Learn what graphs are, how they generalize trees, and the two ways to represent them in code.

Graphs

A graph is a collection of nodes (called vertices) connected by edges. Unlike a tree, a graph has no required root, no parent/child hierarchy, and a node can connect to any number of other nodes — including forming cycles.

Think of a graph like a map of cities connected by roads, or a social network where people are nodes and friendships are edges. Any city can connect to any other city. There is no single "root city."

A tree is actually a special case of a graph — one with no cycles and exactly one path between any two nodes. Graphs are the more general structure.

Graph anatomy

edges go both ways — A↔B

vertices6

edges6

A's neighborsB, C

degree of B3

Vocabulary

Term	Meaning
Vertex (node)	A point in the graph
Edge	A connection between two vertices
Directed	Edges have a direction — A→B does not imply B→A
Undirected	Edges go both ways — A↔B
Weighted	Edges have a cost or distance attached
Unweighted	All edges are treated as equal cost
Cycle	A path that starts and ends at the same vertex
Connected	Every vertex can reach every other vertex
Degree	Number of edges touching a vertex

Directed vs undirected

Undirected:          Directed:
   A —— B                A → B
   |    |                ↑    ↓
   C —— D                C ← D

In an undirected graph, a road between A and B works in both directions. In a directed graph, A→B does not mean you can go from B to A — like a one-way street.

Weighted vs unweighted

Unweighted:           Weighted:
   A —— B                A --5-- B
   |                      |
   C                      3
                           |
                           C

Weighted edges carry a cost — distance, time, price. This matters for shortest path algorithms, covered later in this section.

Representing a graph in code

Adjacency list — most common

Each vertex maps to a list of its neighbors. Efficient for sparse graphs (few edges relative to vertices).

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
}

# weighted version — neighbor paired with edge cost
weighted_graph = {
    "A": [("B", 5), ("C", 3)],
    "B": [("A", 5), ("D", 2)],
    "C": [("A", 3), ("D", 8)],
    "D": [("B", 2), ("C", 8)],
}

Adjacency matrix — simpler, more memory

A 2D grid where matrix[i][j] = 1 means an edge exists between vertex i and vertex j. Wastes memory on sparse graphs but offers O(1) edge lookup.

#      A  B  C  D
# A  [ 0, 1, 1, 0 ]
# B  [ 1, 0, 0, 1 ]
# C  [ 1, 0, 0, 1 ]
# D  [ 0, 1, 1, 0 ]

matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0],
]

# check if edge exists between vertex 0 and vertex 1 — O(1)
has_edge = matrix[0][1] == 1

Adjacency list vs adjacency matrix

	Adjacency List	Adjacency Matrix
Space	O(V + E)	O(V²)
Check if edge exists	O(degree of vertex)	O(1)
Iterate all neighbors	O(degree of vertex)	O(V)
Best for	Sparse graphs (few edges)	Dense graphs (many edges)
Most common in practice	Yes	Less common

Where V is the number of vertices and E is the number of edges.

Most real-world graphs are sparse — a social network with a million users does not have a million friends per person. Adjacency lists are almost always the right default. Use a matrix only when the graph is small and dense, or when O(1) edge lookups matter more than memory.

Real use cases

Social networks — people are vertices, friendships/follows are edges.

Maps and navigation — intersections are vertices, roads are weighted edges. GPS shortest-path routing.

Web crawling — pages are vertices, hyperlinks are directed edges.

Recommendation systems — users and products as vertices, purchases/views as edges.

Dependency resolution — packages are vertices, "depends on" relationships are directed edges. Used in build systems and package managers.

Network routing — routers are vertices, connections are weighted edges based on latency.

What is coming in this section

BFS (Breadth-First Search) — explore level by level using a queue. Finds the shortest path in unweighted graphs.

DFS (Depth-First Search) — explore as deep as possible before backtracking, using a stack or recursion. Used for cycle detection, connectivity, and exploring all paths.

Shortest path — Dijkstra's algorithm for weighted graphs, and other approaches for finding the optimal route between two vertices.

Graphs — Introduction