Breadth-First Search (BFS)

  Breadth-First Search (BFS)

Breadth-first search is a traversal algorithm used for traversing or searching tree or graph data structures. It starts at the root (or some arbitrary node in the case of a graph) and explores all the neighbor nodes at the present depth before moving on to the nodes at the next depth level.

python

# BFS function for a graph

from collections import deque

def bfs(graph, start):

    visited = set()

    queue = deque([start])

    while queue:

        vertex = queue.popleft()

        if vertex not in visited:

            visited.add(vertex)

            queue.extend(graph[vertex] - visited)

    return visited

# BFS function for a binary tree

class Node:

    def __init__(self, val=None, left=None, right=None):

        self.val = val

        self.left = left

        self.right = right

def bfs(root):

    if not root:

        return []

    visited = []

    queue = [root]

    while queue:

        node = queue.pop(0)

        visited.append(node.val)

        if node.left:

            queue.append(node.left)

        if node.right:

            queue.append(node.right)

    return visited