Breadth-First Search (BFS)

Breadth-First Search (BFS) is a foundational algorithm for searching and traversing graph data structures. Instead of diving deep into a specific path, BFS explores the graph layer by layer, moving outwards evenly from the starting node.

         Core Concept:
        BFS uses a Queue (First-In, First-Out or FIFO) to keep track of the nodes
        it needs to visit next. This guarantees that all nodes at the current "depth" (distance from
        the start) are fully explored before the algorithm moves on to nodes at the next depth
        level. It is the perfect algorithm for finding the shortest path in
        unweighted graphs.
      

The Ripple Effect Principle

You can think of BFS like dropping a stone in a pond. The ripples expand uniformly in all directions. Here is how it operates:

Start at your chosen root node, mark it as visited, and add it to the queue.
While the queue is not empty, remove (pop) the node at the front of the queue. This becomes your current node.
Look at all the immediate neighbors of this current node.
If a neighbor hasn't been visited yet, mark it as visited and add it to the back of the queue to be explored later.
Repeat this process until the queue is completely empty.

Algorithm Walkthrough

Below is the Python implementation used in our animation engine. Watch how the queue manages the order of exploration.

def bfs(start_node):
    queue = [start_node]
    visited = [start_node]

    visit(start_node, f"Starting BFS from node {start_node}")

    while len(queue) > 0:
        # Pop from the front of the list (Queue behavior)
        current = queue.pop(0)

        for neighbor in neighbors(current):
            if neighbor not in visited:
                visited.append(neighbor)
                queue.append(neighbor)
                select(neighbor)
                visit(neighbor, f"Exploring {neighbor} from {current}")

# Run the algorithm starting from node '1'
bfs("1")

Complexity

BFS is highly efficient because it guarantees that no node or edge is processed more than once.

Metric	Complexity	Explanation
Time Complexity	$O(V + E)$	Where $V$ is the number of vertices and $E$ is the number of edges. Every vertex is enqueued and dequeued exactly once, and every edge is examined exactly once when its endpoints are visited.
Space Complexity	$O(V)$	The algorithm requires extra memory for the `queue` and the `visited` list. In the worst-case scenario, the queue could hold nearly all vertices in the graph at once.