Breadth-First Search

 Breadth-First Search

Breadth-first search (BFS) is a graph traversal algorithm that explores all the vertices at the present depth before moving on to vertices at the next depth level.

python

# Breadth-first search function

def bfs(graph, start):

    visited = set()

    queue = [start]

    while queue:

        vertex = queue.pop(0)

        if vertex not in visited:

            visited.add(vertex)

            queue.extend(graph[vertex] - visited)

    return visited