data structures~16 minRoute 02 9 of 9

Graphs

Nodes connected by edges — networks, maps, dependencies.

Story — towns connected by roads

A graph is the most general data structure on this site. Take a tree, allow any node to connect to any other node, allow cycles, and you have a graph. Towns connected by roads. People connected by friendships. Web pages connected by links. Twitter follows. Dependency trees that aren't actually trees.

Two parts: nodes (towns, people, pages) and edges (the roads, friendships, links). Edges may be directed (A → B but not B → A — Twitter follows) or undirected (Facebook friends). They may carry weights (driving distance, signal strength).

Graphy says

Two ways to traverse a graph: BFS walks outward in rings (level-by-level — best for shortest path in unweighted graphs). DFS dives one branch all the way down before backtracking (best for connectivity, cycle detection, topological sort).

See it — BFS rings, DFS dives

Pick a start node and watch BFS expand outward — it visits everything at distance 1 before anything at distance 2. Then try DFS — it dives deep, only coming back when it runs out of unseen neighbours.

Pick a start node, then BFS or DFS, then Step.

Start

Graphy says

Two ways to store a graph: an adjacency list (a dict from node to list of neighbours) or an adjacency matrix (a 2D array). The right choice depends on whether your graph is dense or sparse.

Try it — when do you need a graph?

Exercise. Which of these are graphs (not trees)?

(a) A folder hierarchy on disk.
(b) A road network between cities.
(c) A web of pages with hyperlinks.
(d) The call stack at any moment.

Reveal answer

(b) and (c) are graphs — cities have multiple roads connecting them and roads form cycles; web pages link in any direction. (a) and (d) are trees — folders have one parent, the call stack is strictly nested. (Symbolic links can turn (a) into a graph, technically.)

Code it — five languages, one adjacency list

Most code uses an adjacency list — a hash map from node id to a list of neighbour ids. BFS and DFS each fit in about ten lines on top of that representation.

# Adjacency list — most common representation.
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}

# BFS — shortest path in number of hops
from collections import deque
def bfs(start):
    seen = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node)
        for n in graph[node]:
            if n not in seen:
                seen.add(n)
                queue.append(n)

Quiz it — make it stick

Question 1
What's the difference between adjacency list and adjacency matrix representations?
Adjacency list is for directed; matrix is for undirectedList stores neighbours per node (good for sparse); matrix is a 2D bool/weight array (good for dense)There's no differenceMatrix is always faster
True or false — Question 2
On an unweighted graph, BFS always finds the shortest path between two nodes.

Predict — Question 3

On the small graph in this lesson, BFS from A visits nodes in this order:

# graph (undirected):
# A — B
# A — C
# B — D
# C — D
# D — E
# Sample neighbours given in alphabetical order.

Your guess

No Dumb Questions

Real questions other learners asked on this page.

Directed vs undirected — what difference does it make?
Directed edges go one way (Twitter follows). Undirected edges go both ways (Facebook friendships). The data structure is the same shape; the algorithms treat them differently.
What is a weighted graph?
Each edge carries a number — distance, cost, capacity. Weights turn graph problems into optimization: shortest path, minimum spanning tree, max flow. Without weights, BFS finds the shortest path in number of hops.
When do I use BFS vs DFS?
BFS for shortest path in an unweighted graph and for problems that need level-by-level processing. DFS for connectivity, cycle detection, topological sort, and anything that fits a "explore one branch fully before backtracking" mental model.