Graphs in Python: Adjacency List, BFS and DFS

A graph is a set of things and the connections between them. The things are called nodes (or vertices) and the connections are called edges. A map is a graph: cities are nodes and roads are edges. So is a social network (people and friendships), the web (pages and links), or a list of tasks where some must happen before others.

This guide shows how to store a graph in Python, and how to explore it with the two basic searches, BFS and DFS. Then it applies them to real problems: shortest path, connected components, counting islands, cycle detection and ordering tasks. All the output shown is real.

Graph vocabulary

A tree is a graph too: one that is connected and has no cycles. Everything in Binary Tree in Python: Traversals Explained is a special case of what follows.

Storing a graph: adjacency list

The most common way to store a graph in Python is a dictionary. Each key is a node, and each value is the list of nodes it connects to. Because we start from a list of edges, we write a small helper that builds it. For an undirected graph every edge is stored in both directions:

from collections import deque

def build_graph(edges, directed=False, nodes=()):
    graph = {n: [] for n in nodes}
    for a, b in edges:
        graph.setdefault(a, []).append(b)
        graph.setdefault(b, [])
        if not directed:
            graph[b].append(a)
    return graph

edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]
g = build_graph(edges)

print(g)
print(g["D"])
print(len(g), sum(len(v) for v in g.values()) // 2)

Output

{'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C', 'E'], 'E': ['D']}
['B', 'C', 'E']
5 5

Here is the same graph drawn out:

A --- B
|     |
C --- D --- E

For a directed graph, an edge is stored once, from the start to the end. Here is a small “who follows whom” example, and finding who follows a node needs a scan of everything:

follows = build_graph([("asha", "ben"), ("ben", "chen"), ("chen", "asha"), ("asha", "chen")], directed=True)
print(follows)
print("asha follows:", follows["asha"])
print("who follows chen:", [n for n in follows if "chen" in follows[n]])

Output

{'asha': ['ben', 'chen'], 'ben': ['chen'], 'chen': ['asha']}
asha follows: ['ben', 'chen']
who follows chen: ['asha', 'ben']

For a weighted graph, store the weight next to each neighbour, usually as a tuple:

roads = {
    "Delhi":  [("Jaipur", 280), ("Agra", 230)],
    "Jaipur": [("Delhi", 280), ("Agra", 240)],
    "Agra":   [("Delhi", 230), ("Jaipur", 240)],
}
for city, links in roads.items():
    print(city, "->", [name for name, km in links])
print(min(roads["Delhi"], key=lambda link: link[1]))

Output

Delhi -> ['Jaipur', 'Agra']
Jaipur -> ['Delhi', 'Agra']
Agra -> ['Delhi', 'Jaipur']
('Agra', 230)

Adjacency matrix

The alternative is a grid of size V x V. Row a, column b holds 1 if there is an edge from a to b, and 0 if not:

names = list(g)
index = {n: i for i, n in enumerate(names)}
matrix = [[0] * len(names) for _ in names]
for a in g:
    for b in g[a]:
        matrix[index[a]][index[b]] = 1

print("   ", *names)
for name, row in zip(names, matrix):
    print(name, " ", *row)
print(matrix[index["A"]][index["B"]], matrix[index["A"]][index["E"]])

Output

    A B C D E
A   0 1 1 0 0
B   1 0 0 1 0
C   1 0 0 1 0
D   0 1 1 0 1
E   0 0 0 1 0
1 0

Most real graphs are sparse, meaning each node connects to only a few others, so the adjacency list wins on memory and on neighbour lookups. We use it for the rest of the post.

BFS: breadth-first search

BFS visits the start, then all its neighbours, then all their neighbours, and so on, like ripples in water. A queue does exactly this: nodes are processed in the order they were discovered. Use a deque (see Queue and Deque in Python Explained):

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)          # mark when adding, not when removing
                queue.append(nb)
    return order

print(bfs(g, "A"))
print(bfs(g, "E"))

Output

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

The visited set is what keeps the search from going round in circles. Note that a node is marked when it is added to the queue, not when it is removed. Otherwise the same node could be queued several times. Starting at E gives a different order, as expected.

Shortest path with BFS

Since BFS explores in rings, the first time it reaches a node is along the path with the fewest edges. To get the actual path, remember for each node which node it was reached from (the parent), then walk back from the goal. Or simply store the number of steps:

def distances(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nb in graph[node]:
            if nb not in dist:
                dist[nb] = dist[node] + 1
                queue.append(nb)
    return dist

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

print(distances(g, "A"))
print(shortest_path(g, "A", "E"))
print(shortest_path(build_graph(edges, nodes=["Z"]), "A", "Z"))

Output

{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 3}
['A', 'B', 'D', 'E']
None

This works for unweighted graphs, where every edge counts as one step. If edges have different costs, you need Dijkstra’s algorithm, which is BFS with a priority queue (see Heap and heapq in Python: Priority Queues). Returning None means the goal cannot be reached at all.

DFS: depth-first search

DFS picks one neighbour and keeps going deeper until it hits a dead end, then backs up and tries the next neighbour. It is the natural recursive solution, and it can also be written with an explicit stack (see Stack in Python):

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    order = [node]
    for nb in graph[node]:
        if nb not in visited:
            order += dfs(graph, nb, visited)
    return order

def dfs_iter(graph, start):
    visited, order = set(), []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for nb in reversed(graph[node]):
            if nb not in visited:
                stack.append(nb)
    return order

print(dfs(g, "A"))
print(dfs_iter(g, "A"))

Output

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

Both versions give the same order here. The iterative one pushes neighbours in reverse, so that the first neighbour is popped first. The recursive version is shorter, but very deep graphs can hit Python’s recursion limit (see Recursion in Python Explained Simply). Only the container differs between the two searches: a queue gives BFS and a stack gives DFS.

Problems you can solve

Is there a path? Any search will tell you. Reach the goal, and the answer is yes. Run out of nodes, and the answer is no:

def has_path(graph, start, goal):
    visited = {start}
    stack = [start]
    while stack:
        node = stack.pop()
        if node == goal:
            return True
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                stack.append(nb)
    return False

two_parts = build_graph([("A", "B"), ("C", "D")])
print(has_path(g, "A", "E"))
print(has_path(two_parts, "A", "D"))

Output

True
False

How many separate groups (connected components)? Start a search from every node not yet visited. Each new search finds one whole group. Node 6 below has no edges, so it counts as a group by itself. Pass all nodes in explicitly, since nodes without edges do not appear in the edge list:

def count_components(graph):
    visited = set()
    count = 0
    for node in graph:                   # start a new search for every unvisited node
        if node not in visited:
            count += 1
            visited.add(node)
            stack = [node]
            while stack:
                cur = stack.pop()
                for nb in graph[cur]:
                    if nb not in visited:
                        visited.add(nb)
                        stack.append(nb)
    return count

graph = build_graph([(1, 2), (2, 3), (4, 5)], nodes=[1, 2, 3, 4, 5, 6])
print(count_components(graph))

Output

3

Number of islands. A grid is a graph too: each cell connects to the cells above, below, left and right. Count the groups of connected 1s. The search “sinks” each island once it has found it. Cells that touch only diagonally are not connected:

def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = set()

    def sink(r, c):
        if not (0 <= r < rows and 0 <= c < cols):
            return
        if grid[r][c] != "1" or (r, c) in seen:
            return
        seen.add((r, c))
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            sink(r + dr, c + dc)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                count += 1
                sink(r, c)
    return count

grid = [
    "11000",
    "11000",
    "00100",
    "00011",
]
print(count_islands(grid))

Output

3

Does the graph have a cycle? In an undirected graph, run DFS and remember which node you came from. If you reach an already visited node that is not your parent, you have found a cycle:

def has_cycle(graph):
    visited = set()

    def dfs(node, parent):
        visited.add(node)
        for nb in graph[node]:
            if nb == parent:
                continue
            if nb in visited or dfs(nb, node):
                return True
        return False

    return any(node not in visited and dfs(node, None) for node in graph)

triangle = build_graph([("A", "B"), ("B", "C"), ("C", "A")])
chain = build_graph([("A", "B"), ("B", "C")])
print(has_cycle(triangle), has_cycle(chain))

Output

True False

In what order can tasks be done? If a directed graph says “A must come before B”, a topological sort gives a valid order. Repeatedly take a node that has no unfinished prerequisites (indegree 0), then remove its outgoing edges. If some nodes are left over, the tasks depend on each other in a circle, and no order exists. This is how build systems and course schedulers work:

def topo_sort(graph):
    indegree = {n: 0 for n in graph}
    for n in graph:
        for nb in graph[n]:
            indegree[nb] += 1
    queue = deque(n for n in graph if indegree[n] == 0)
    order = []
    while queue:
        n = queue.popleft()
        order.append(n)
        for nb in graph[n]:
            indegree[nb] -= 1
            if indegree[nb] == 0:
                queue.append(nb)
    return order if len(order) == len(graph) else None

tasks = build_graph([("A", "B"), ("A", "C"), ("B", "D"), ("C", "D")], directed=True)
print(topo_sort(tasks))
loop = build_graph([("A", "B"), ("B", "C"), ("C", "A")], directed=True)
print(topo_sort(loop))

Output

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

BFS or DFS?

Complexity

With an adjacency list, both searches look at each node once and follow each edge once (twice in an undirected graph). The time is O(V + E), where V is the number of nodes and E the number of edges. The extra memory is O(V) for the visited set and the queue or stack. With an adjacency matrix the time becomes O(V x V), because finding neighbours means scanning a full row. See Big O Notation in Python if this notation is new.

Common mistakes

• No visited set. Any cycle, and every undirected edge, sends the search back where it came from, so it never finishes.
• Marking visited too late in BFS. Mark a node when you add it to the queue, not when you pop it.
• Only searching from one start node. A disconnected graph needs a loop over all nodes to reach every part.
• Forgetting the reverse edge. In an undirected graph, add both a to b and b to a.
• Nodes with no edges. They are missing from the graph unless you add them explicitly, as the nodes argument does above.
• Using a list as a queue. list.pop(0) is O(n). Use deque.popleft().
• Expecting BFS to work with weights. BFS counts edges, not costs. Use Dijkstra for weighted paths.

Try it yourself

Work out each answer first, then open the solution. The graph g from above is assumed (A-B, A-C, B-D, C-D, D-E).

1. Compute the degree of every node and find the node with the most connections.

degree = {n: len(nbs) for n, nbs in g.items()}
print(degree)
print(max(degree, key=degree.get))

{'A': 2, 'B': 2, 'C': 2, 'D': 3, 'E': 1}
D

2. Return all nodes exactly k steps away from a start node.

def at_distance(graph, start, k):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nb in graph[node]:
            if nb not in dist:
                dist[nb] = dist[node] + 1
                queue.append(nb)
    return [n for n, d in dist.items() if d == k]

print(at_distance(g, "A", 2), at_distance(g, "A", 3))

['D'] ['E']

3. Which search would you use to find the fewest flights between two cities, and why?

4. Why does a graph search need a visited set, but a tree traversal usually does not?

Run these in our free Python compiler.

Frequently asked questions

How do you represent a graph in Python?

Usually as an adjacency list: a dictionary that maps every node to a list of its neighbours. An adjacency matrix (a list of lists of 0 and 1) is the alternative for small or dense graphs.

What is the difference between BFS and DFS?

BFS explores level by level using a queue, so it finds the shortest path in an unweighted graph. DFS goes as deep as possible first using a stack or recursion, and suits cycle detection, ordering and exploring everything.

What is the time complexity of BFS and DFS?

O(V + E) with an adjacency list, where V is the number of nodes and E the number of edges. Each node and each edge is processed once.

How do you find the shortest path in a graph in Python?

For an unweighted graph, use BFS and record each node’s parent or distance. For weighted edges, use Dijkstra’s algorithm with a heap.

How do you detect a cycle in a graph?

In an undirected graph, run DFS and report a cycle when you reach a visited node that is not the one you came from. In a directed graph, a topological sort that cannot include every node shows a cycle.

Why do I need a visited set?

Graphs can contain cycles, and undirected edges point both ways. Without a visited set the search would keep returning to nodes it has already handled and might never finish.

Related reading

• Queue and Deque in Python Explained – the tool behind BFS.
• Stack in Python: Implementation and Uses – the tool behind iterative DFS.
• Heap and heapq in Python: Priority Queues – Dijkstra and weighted paths.
• Recursion in Python Explained Simply – how recursive DFS works.