Python programs / Graphs / Breadth-first search

Python Program for Breadth-First Search (BFS)

Intermediate Graphs Time O(V + E) Space O(V)

Visits the nodes of a graph from a start node, nearest first, keeping the nodes still to visit in a queue.

Breadth-first search (BFS) visits the nodes of a graph in rings around a start node: first the start, then every node one edge away, then every node two edges away, and so on. The program's graph has six nodes and six edges (A–B, A–C, B–D, B–E, C–F and E–F), and BFS from A visits A, then B and C, then D, E and F. Because it reaches every node by the fewest edges possible, BFS is how you find the shortest route when every step counts the same: moves in a puzzle, friends of friends, links between web pages.

Program

from collections import deque


def bfs(graph, start):
    """Every node reachable from start, nearest first."""
    order = []
    seen = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)  # so it's queued only once
                queue.append(neighbour)
    return order


# Each node, and the nodes it's joined to by an edge
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}
print("BFS from A:", bfs(graph, "A"))

Open in the editor Download breadth_first_search.py

Output

BFS from A: ['A', 'B', 'C', 'D', 'E', 'F']

How it works

  1. deque from the collections module is a queue: adding at the back and taking from the front are both fast. A plain list would have to move every item along each time its first one is taken.
  2. order collects the nodes as they are visited, seen holds every node found so far (a set answers "is it in here?" at once), and the queue starts with the start node.
  3. While the queue isn't empty, the node at its front is taken off and visited: added to order.
  4. Each neighbour not seen yet is marked as seen and goes to the back of the queue, behind the nodes found before it. That's what makes the search go ring by ring. Marking a node when it's queued, not when it's visited, keeps it from going in twice: F is a neighbour of both C and E, but it's queued only once.
  5. When the queue is empty, every node the start can reach has been visited, and the function returns them in order.
  6. The graph is a dictionary: each node is a key, and its value is the list of nodes it's joined to. An edge goes both ways, so it's listed twice: B is in A's list and A is in B's.
  7. The program prints the order BFS visits the nodes in, starting from A.

The queue after each visit, starting from A:

Step Visits Adds to the queue Queue after
1 A B, C B, C
2 B D, E (A is seen) C, D, E
3 C F (A is seen) D, E, F
4 D nothing E, F
5 E nothing (B and F are seen) F
6 F nothing empty

The nodes leave the queue a ring at a time: A, then B and C (one edge from A), then D, E and F (two edges).

Time and space complexity

TimeO(V + E)
Extra spaceO(V)

Each node goes into the queue once and comes out once, so the while loop runs at most V times for a graph of V nodes. Each time, it reads that node's list of neighbours, and all the lists together hold every edge twice (once from each end), so the inner loop runs about 2E times in all for E edges. Together that's O(V + E). seen, the queue and order each hold at most every node, so the extra space is O(V). The set matters here: neighbour not in seen takes the same short time however many nodes it holds, where a list would be searched item by item.

Other ways to write it

Finding the path with the fewest edges

A dict, parent, records which node each one was found from, and does the job of seen too. When the goal comes off the queue, following parent back to the start gives the path. BFS finds the goal by the fewest edges first, so from A to F the path is A, C, F (2 edges), not A, B, E, F (3).

from collections import deque

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 neighbour in graph[node]:
            if neighbour not in parent:
                parent[neighbour] = node
                queue.append(neighbour)
    return None

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

Try it yourself

  • Start from D instead of A. The order becomes D, B, A, E, C, F: B is one edge away, A and E two, C and F three.
  • Add a node that nothing is joined to, "G": []. BFS from A never reaches it, so it isn't in the result.
  • Count each node's distance in edges from the start: make seen a dict, {start: 0}, put seen[neighbour] = seen[node] + 1 in place of seen.add(neighbour), and return seen. From A, B and C are 1 edge away and D, E and F are 2.
  • Change popleft() to pop(), which takes from the back, so the queue becomes a stack. The order changes to A, C, F, E, B, D: the search now follows one path deep before trying the others.

More graphs programs

Share this program