Data Structures · Lesson 7 of 8

Graphs

Vertices, edges, adjacency lists, BFS and DFS intuition.

• Advanced
• 16 min read
• 3 objectives

Before this lessonLesson 6: Hash Tables

A graph is a set of vertices (nodes) joined by edges. It models anything made of connections: roads between cities, friends in a social network, links between web pages, packages that depend on other packages. A tree is just a graph with no cycles and one root.

Anything connected is a graph

A graph is just things (nodes, or vertices) and connections between them (edges). Friends on a social network, cities joined by roads, web pages linking to each other, tasks that depend on other tasks: all graphs. Trees are a special, well-behaved kind of graph. Graph algorithms answer questions such as "is there a route from A to B?", "what is the shortest route?" and "who are the friends of friends?"

Kinds of graphs

• Undirected: an edge works both ways (friendship). Directed: an edge has a direction (follows, links to).
• Weighted: edges carry a cost such as distance or time.
• Cyclic or acyclic: whether you can follow edges and return to where you started. A directed acyclic graph (DAG) models task dependencies.

Representing a graph

The most common representation is an adjacency list: a dictionary mapping each vertex to a list of its neighbors. It uses space proportional to vertices plus edges and is fast to iterate, which suits most real graphs.

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

['B', 'C']

An adjacency matrix (a 2D grid of yes/no) answers "is there an edge between X and Y?" in O(1) but uses V squared memory, so it fits only dense graphs.

Breadth-first search (BFS)

BFS explores all neighbors before going deeper, using a queue. In an unweighted graph it finds the path with the fewest edges. Track visited nodes so you never loop forever on a cycle.

from collections import deque

def bfs(start):
    seen = {start}
    q = deque([start])
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                q.append(nxt)
    return order

print(bfs("A"))

['A', 'B', 'C', 'D']

Depth-first search (DFS)

DFS follows one path as far as it goes before backing up, using recursion or a stack. It is the basis for cycle detection, topological sorting and finding connected components.

def dfs(node, seen=None):
    seen = seen if seen is not None else set()
    seen.add(node)
    for nxt in graph[node]:
        if nxt not in seen:
            dfs(nxt, seen)
    return seen

print(sorted(dfs("A")))

['A', 'B', 'C', 'D']

Both BFS and DFS run in O(V + E): every vertex and edge is examined at most once.

Where to go next

• Dijkstra: shortest paths with weighted edges.
• Topological sort: order tasks so dependencies come first.
• Union-Find: quickly answer whether two nodes are connected.

Store a graph as an adjacency list

The most common representation is a dictionary that maps each node to the list of its neighbours.

graph = {
    "Ada":   ["Linus", "Grace"],
    "Linus": ["Ada", "Alan"],
    "Grace": ["Ada", "Alan"],
    "Alan":  ["Linus", "Grace", "Tim"],
    "Tim":   ["Alan"],
}

print(graph["Alan"])
print(len(graph["Ada"]), "friends")

['Linus', 'Grace', 'Tim']
2 friends

Breadth-first search finds the shortest path

BFS explores all neighbours first, then their neighbours, spreading outward one layer at a time like ripples in a pond. Because it visits nearer nodes before farther ones, the first time it reaches a target it has found the route with the fewest hops.

from collections import deque

graph = {
    "Ada": ["Linus", "Grace"], "Linus": ["Ada", "Alan"],
    "Grace": ["Ada", "Alan"], "Alan": ["Linus", "Grace", "Tim"], "Tim": ["Alan"],
}

def shortest_path(start, goal):
    queue = deque([[start]])
    seen = {start}
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == goal:
            return path
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(path + [nxt])
    return None

print(shortest_path("Ada", "Tim"))

['Ada', 'Linus', 'Alan', 'Tim']

Why the seen set is essential

Graphs can contain loops (Ada knows Linus, Linus knows Ada). Without remembering visited nodes, the search would walk in circles forever. Marking nodes as seen the moment you queue them keeps every node visited at most once.

Depth-first search explores one branch fully

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

def dfs(node, seen=None):
    seen = seen if seen is not None else []
    seen.append(node)
    for nxt in graph[node]:
        if nxt not in seen:
            dfs(nxt, seen)
    return seen

print(dfs("A"))

['A', 'B', 'D', 'C']

Key takeaways

• A graph is nodes plus edges; store it as a dict of neighbour lists.
• BFS uses a queue and finds shortest paths in unweighted graphs; DFS uses recursion (or a stack) and explores deeply.
• Always track visited nodes to avoid infinite loops.

# Write your solution here