Breadth-First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. It explores the graph layer by layer.

BFS is typically implemented using a queue. It's particularly useful for finding the shortest path between two nodes in an unweighted graph. The time complexity is O(V + E), where V is the number of vertices and E is the number of edges.

BFS Traversal (Graph)

Step 1 of 0

Action

Ready to start

Current Node

None

Queue

[]

Traversal Order

[]

Start Node

Current Node

Visited

In Queue

Unvisited

Traversed Edge

Breadth-First Search (BFS) for Graphs

Breadth-First Search (BFS) in graphs explores neighbors first before moving to the next level. It's excellent for finding the shortest path in an unweighted graph.

Algorithm Steps

Create a queue and add the starting node to it.
Create a set to store visited nodes to avoid cycles.
While the queue is not empty, do the following:
Dequeue a node and process it.
For each of its unvisited neighbors, mark them as visited and enqueue them.
Repeat until the queue is empty.

Graph BFS


from collections import deque

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    visited.add(start_node)
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result