Breadth-First Search (BFS) algorithm with 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.

1. We change the name – this is just for readability, but readability counts. So, the name stack is changed tp queue.
2. 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)
3. 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

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! 🙂