AI Hints
DSA in Python · Lesson 78 of 132

Breadth First Search

Exploring in rings.

⏱ 2 min read▶ Video at 1:32:11🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Breadth first search explores a graph in rings. First the starting node, then all its neighbours, then their neighbours, and so on. Like ripples spreading out in a pond. It's the same idea as level order in a tree, with one extra detail.

Breadth First Search
From the video: Breadth First Search
  • Explore in rings
  • Like ripples in a pond
  • One extra detail

BFS with a visited set

The extra detail is a visited set. Graphs can have cycles, so without it, we'd go round in circles forever. We start from Ana. Each time we take someone from the front of the queue, we add any friends we haven't seen yet to the back. Run it. Ana's friends come first, then friends of friends.

bfs.pypython
from collections import deque
from graph import friends

def bfs(start):
    visited, queue, order = {start}, deque([start]), []
    while queue:
        person = queue.popleft()
        order.append(person)
        for f in friends[person]:
            if f not in visited:
                visited.add(f)
                queue.append(f)
    return order

print(bfs("Ana"))
Output
['Ana', 'Ben', 'Cara', 'Dev', 'Eli', 'Fay']
Also uses graph.py
friends = {
    "Ana":   ["Ben", "Cara"],
    "Ben":   ["Ana", "Dev"],
    "Cara":  ["Ana", "Dev", "Eli"],
    "Dev":   ["Ben", "Cara", "Fay"],
    "Eli":   ["Cara"],
    "Fay":   ["Dev"],
}

BFS facts

Breadth first search visits every node and every edge once, so it's O of V plus E, the number of nodes plus the number of edges. It always reaches nearer nodes before farther ones. That makes it perfect for finding the shortest path, when every edge counts the same.

keyvalue
Usesa queue + visited set
Ordernearest first
CostO(V + E)
Great forshortest paths

Summary

Breadth first search uses a queue and a visited set to explore a graph in rings, nearest first. Next, depth first search.

Key takeaways
  • Queue
  • Visited set
  • Nearest first
Next up: Depth First Search — going deep first