Description

Breadth First Search is a algorithm for searching a graph one "level" at a time. Its a Level Order Traversal for graphs and is often used for finding the shortest distance to a node. It does this by using a Queue

Runtime

O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph

Visualization

Pseudocode

Add the start node to a queue
While there is a value in the queue
	Dequeue the first node
	If the node is the one we are looking for, return
	If it is not,
		Mark it as visited
		Add its neighbors to the queue
If the queue is empty and you didnt find it, there is no path to it.

Code

def bfs(start, target, graph):
    explored = {start: True}  # Mark start as explored immediately
    queue = [(start, 0)]  # (node, depth)

    while queue:
        key, depth = queue.pop(0)
        if key == target:
            return depth

        for node in graph[key].neighbors:
            if node not in explored:
                queue.append((node, depth + 1))
                explored[node] = True  # Mark as explored immediately when enqueuing

    return -1  # Return -1 if target is not reachable