What is a breadth-first search algorithm?

Breadth-First Search (BFS) is a graph or tree traversal or search method where all vertices at the current level are visited first, then the algorithm proceeds to the vertices at the next level.

Main features:

• Uses a queue to store vertices to be visited.
• Starts from the source vertex, adding it to the queue.
• While the queue is not empty, it dequeues a vertex, visits its neighbors that have not been visited yet, and adds them to the queue.

Example of application: finding the shortest path in an unweighted graph.

Python example:

from collections import deque

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

    while queue:
        vertex = queue.popleft()
        print(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Example graph
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph, 'A')