Editor

Python Program for Breadth-First Search on a Graph

Intermediate · Data structures

A graph is a set of nodes joined by edges, like cities joined by roads or people joined by friendships. Breadth-first search (BFS) explores a graph level by level: first the starting node, then all its neighbours, then their neighbours, and so on. It uses a queue, so nodes are explored in the order they were found.

Program

graph_bfs.py
from collections import deque
# A
# / \
# B C
# / \ \
# D E---F
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"],
}
def bfs(graph, start):
visited = {start} # nodes already found, so none is queued twice
queue = deque([start]) # nodes waiting to be explored
order = []
while queue: # stop when the queue is empty
node = queue.popleft() # take the oldest node in the queue
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
print("Visit", node, "| queue now:", list(queue))
return order
print("BFS order from A:", " ".join(bfs(graph, "A")))
Output
Visit A | queue now: ['B', 'C']
Visit B | queue now: ['C', 'D', 'E']
Visit C | queue now: ['D', 'E', 'F']
Visit D | queue now: ['E', 'F']
Visit E | queue now: ['F']
Visit F | queue now: []
BFS order from A: A B C D E F

How it works

  1. The graph is stored as a dictionary called an adjacency list: each key is a node, and its value lists the nodes it is joined to.
  2. The queue starts with just A, and each round takes the oldest node from the front with popleft() and adds its unvisited neighbours at the back.
  3. Because a queue is first in, first out, A's neighbours B and C are explored before any node two steps away, like D, E and F.
  4. The visited set remembers every node already found, so F, which is joined to both C and E, is queued only once and the search cannot go round in circles.
  5. The loop ends when the queue is empty, which means every node that can be reached from A has been visited.

Another way to write it

Shortest path between two nodes

Shortest path between two nodes
from collections import deque
graph = {"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
"D": ["B"], "E": ["B", "F"], "F": ["C", "E"], "G": []}
def shortest_path(start, goal):
came_from = {start: None} # each node remembers who found it
queue = deque([start])
while queue:
node = queue.popleft()
if node == goal: # walk back from the goal to the start
path = []
while node is not None:
path.append(node)
node = came_from[node]
return " -> ".join(reversed(path))
for neighbour in graph[node]:
if neighbour not in came_from:
came_from[neighbour] = node
queue.append(neighbour)
return "no path" # the queue ran out first
print("A to F:", shortest_path("A", "F"))
print("D to F:", shortest_path("D", "F"))
print("A to G:", shortest_path("A", "G"))
Output
A to F: A -> C -> F
D to F: D -> B -> E -> F
A to G: no path

BFS reaches every node by the fewest possible edges, so remembering which node found each one gives the shortest route, and G, which has no edges, makes the queue run out with no path found.

Try it yourself

Add a node "G" joined to "D" (in both lists) and check where it appears in the BFS order.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises