Lesson 10 of 14

Graphs and Traversal

Friendships and transit networks do not divide neatly under one parent. Many locations connect, and a route may loop back to its start. A graph represents these relationships.

• Vertex: An entity such as a person or station.
• Edge: A connection between vertices. Directed edges form a directed graph.
• Weight: A cost attached to an edge, such as travel time.

Two ways to store connections

An adjacency list stores each vertex’s neighbors. With V vertices and E edges, it uses O(V+E) space. An adjacency matrix stores connections in a table using O(V²) space. A matrix makes checking a particular connection direct, but requires the whole table even when connections are sparse.

BFS explores nearby vertices first

Breadth-first search (BFS) uses a queue. It visits the starting vertex’s neighbors, then their neighbors. This example lists each undirected connection in both directions.

from collections import deque

graph = {
    "A": ["B", "C"], "B": ["A", "D"],
    "C": ["A", "D"], "D": ["B", "C"]
}
queue = deque(["A"])
seen = {"A"}

while queue:
    node = queue.popleft()
    print(node)
    for neighbor in graph[node]:
        if neighbor not in seen:
            seen.add(neighbor)
            queue.append(neighbor)

The output is A B C D. Both B and C lead to D, but marking a vertex when it is enqueued prevents adding D twice. Traversal order can vary with the order of neighbors.

DFS goes deep, then returns

Depth-first search (DFS) follows one branch as far as possible before returning. It uses a stack or recursion. Choosing B first in this graph can produce A B D C.

With adjacency lists and average O(1) visited checks, BFS and DFS take O(V+E). Starting from one vertex visits only reachable vertices. To cover an entire disconnected graph, restart from unvisited vertices.

Check your understanding

What goes wrong without marking visited vertices? What cost does a shortest path found by BFS minimize?