Breadth-First Search (BFS) algorithm with Python

Posted on December 3, 2025 by

Vitosh Posted in Python

BFS, DFS, A-Star – these sound like magic spells from a Harry Potter book! And actually, these are magical (especially the A-Star) as far as they are well-defined algorithms, that explore a graph. In our previous article, we have explored Depth-First Search (DFS) and we learned how to dive deep into a graph, using a Stack to keep trach of our path. It was like exloring a maze by running as far as possible until we hit a wall.

Today, we are going to perform a little magic trick (go Hermione) – with just three lines of code, we will transform that deep-diving explorer into a BFS scanner.

Indstead of diving deep, BFS spreads out like water. It checks all immediate neighbours first, before moving to the next level. This guarantees that if a path exists, BFS will find the one with the fewest steps (but not for an optimal amount of time, of course).

The 3 Changes:

To turn our Python DFS code into BFS, we need to modify how to treat our list.

We change the name – this is just for readability, but readability counts. So, the name stack is changed tp queue.
Change the Pop function:
- DFS – node = stack.pop(), taking from the end (index-1)
- BFS – node = queue.pop(0), taking from the start (index 0)
Changing the Neighbor Order – In DFS we had reversed the neighbors, so the LIFO was implemented correctly. Now we do not need that.
- DFS – for n in reversed(neighbors):
- BFS – for n in neighbors:

Ok, so, out of the 3 changes only 1 was actually really useful and mattered a lot – the pop(0). But the other 2 also helped a bit, at least for the general understanding.

The code is below:

def dfs_normal(raw_data):
    lines = raw_data.strip().split('\n')   
    n_edges = int(lines[0].split()[0])
    edge_lines = lines[1:1+n_edges]
    start, end = lines[-1].split()
    
    print(f"Finding a path from {start} to {end}!")
    print("-" * 50)
    graph = {}

    for line in edge_lines:
        u, v, _ = line.split()
        if u not in graph:
            graph[u] = []
        if v not in graph:
            graph[v] = []
        graph[u].append(v)

    stack = [start]
    visited = set()
    visited_sequence = []
    parents = {start: None}
    step = 0

    while stack:
        node = stack.pop()
    
        if node == end:
            visited_sequence.append(node)
            break
        if node not in visited:
            step += 1
            visited_sequence.append(node)
            print(f'Step {step}: visiting {node}')
            
            visited.add(node)
            neighbors = graph.get(node, [])
            
            for n in reversed(neighbors):
                if n not in visited_sequence:
                    stack.append(n)
                    if n not in parents:
                        parents[n] = node
    
    print("-" * 50)
    if end in visited_sequence:
        print("Reconstructing the path to home! :)")
        path = []
        current = end

        while current is not None:
            path.append(current)
            current = parents[current]
        path.reverse()
        print(f'Final path: {" -> ".join(path)}')
        print(f'Total Nodes Visited: {len(visited_sequence)}.')
        print(f'Path length: {len(path)}.')
        
    else:
        return False
                
    return True

def dfs_normal(raw_data):

lines = raw_data.strip().split('\n')

n_edges = int(lines[0].split()[0])

edge_lines = lines[1:1+n_edges]

start, end = lines[-1].split()

print(f"Finding a path from {start} to {end}!")

print("-" * 50)

graph = {}

for line in edge_lines:

u, v, _ = line.split()

if u not in graph:

graph[u] = []

if v not in graph:

graph[v] = []

graph[u].append(v)

stack = [start]

visited = set()

visited_sequence = []

parents = {start: None}

step = 0

while stack:

node = stack.pop()

if node == end:

visited_sequence.append(node)

break

if node not in visited:

step += 1

visited_sequence.append(node)

print(f'Step {step}: visiting {node}')

visited.add(node)

neighbors = graph.get(node, [])

for n in reversed(neighbors):

if n not in visited_sequence:

stack.append(n)

if n not in parents:

parents[n] = node

print("-" * 50)

if end in visited_sequence:

print("Reconstructing the path to home! :)")

path = []

current = end

while current is not None:

path.append(current)

current = parents[current]

path.reverse()

print(f'Final path: {" -> ".join(path)}')

print(f'Total Nodes Visited: {len(visited_sequence)}.')

print(f'Path length: {len(path)}.')

else:

return False

return True

filename = "graph_data.txt"
with open(filename, "r") as file:
    raw_data = file.read()
dfs_normal(raw_data)

filename = "graph_data.txt"

with open(filename, "r") as file:

raw_data = file.read()

dfs_normal(raw_data)

And a few more points, describing the BFS algorithm:

Optimal? Yes!
- For unweighted graphs, as the one in the article
Complete? Yes!
- If there is a way, it will be found.
Worst-case performance – O(|V|+|E|)
- We visit every vertex V and every edge E once.
Worst-case space complexity – O(|V|)
- We might have to store almost all nodes in the queue at once. If all roads lead directly to it.

The GitHub project is here: https://github.com/Vitosh/Python_personal/tree/master/YouTube/048_Python-Graph

Enjoy it! 🙂