Graph

#How does it work?

A graph consists of nodes (vertices) and the edges that connect them. Road maps, social networks, computer networks and links between web pages are all modelled as graphs.

Edges can be directed (a one-way street, following someone) or undirected (a two-way road, friendship), and can carry weights (distance, cost). This lesson uses an undirected, unweighted graph.

Graphs are usually stored as adjacency lists: each node keeps a list of its neighbours. The alternative is an adjacency matrix: an n×n table with a 1 where an edge between i and j exists. The two basic ways to explore a graph are breadth-first search (BFS) and depth-first search (DFS).

#Try it yourself

#Basic operations

BFS(start)

Spreads out from the start layer by layer: first all neighbours, then their neighbours. Uses a queue. Finds shortest paths (fewest edges) in unweighted graphs.

DFS(start)

Goes as deep as possible along one path, then backtracks at dead ends. Uses recursion or a stack. The basis of cycle detection, connected components and topological sorting.

addEdge(u, v)

In an undirected graph, adds v to u's adjacency list and u to v's.

removeEdge(u, v)

Removes the edge from both adjacency lists.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

from collections import deque

# Adjacency list: graph[u] holds u's neighbours.
graph: dict[int, list[int]] = {node: [] for node in range(1, 8)}
for u, v in [(1, 2), (1, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 7), (5, 7), (6, 7)]:
    graph[u].append(v)  # undirected: add both directions
    graph[v].append(u)


def bfs(start: int) -> list[int]:
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            if v not in visited:  # mark when queued so each node is queued once
                visited.add(v)
                queue.append(v)
    return order


def dfs(u: int, visited: set[int], order: list[int]) -> list[int]:
    visited.add(u)
    order.append(u)
    for v in graph[u]:
        if v not in visited:
            dfs(v, visited, order)
    return order


print(*bfs(1))  # layer by layer
print(*dfs(1, set(), []))  # as deep as possible, then backtrack

#Complexity

V is the number of nodes and E the number of edges. BFS and DFS visit every node once and look at every edge (from both ends in an undirected graph): O(V + E). Adjacency lists use far less memory for sparse graphs (few edges); a matrix is preferred for dense graphs or when edge lookups are very frequent.

#When to use it?

Shortest routes in navigation (Dijkstra, A*), "people you may know" in social networks (second-degree neighbours via BFS), web crawlers, build order in compilers (topological sort), maze solving and network connectivity analysis all rely on graph algorithms.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Union-Find