Discover, Locate, Learn: Python's Breadth First Search Demystified.

Breadth First Search use case.


Breadth First search is also called a level order traversal. BFS is an algorithm to traverse the graph level by level. While traversing the algorithm visits all vertices and edges, any node is taken as a root node during traversal starting. For BF search a queue data structure would be used that follows FIFO(First In First Out) principle.

Breadth First Search algorithm.
Breadth First Search meme.

Python Knowledge Base: Make coding great again.
- Updated: 2024-12-01 by Andrey BRATUS, Senior Data Analyst.




    The process organised in such a way that we visit nodes level wise, i e first we complete the top level and then move on to lower levels. The practical example of BFS use case is a chess game engine where we build the game tree from the current position and apply all possible moves to find a win position. Breadth-first search finds a solution node if one exists.


  1. Breadth First Search Python code:


  2. 
    import collections
    
    # BFS function
    def bfs(graph, root):
    
        visited, queue = set(), collections.deque([root])
        visited.add(root)
    
        while queue:
    
            # Dequeue a vertex from queue
            vertex = queue.popleft()
            print(str(vertex) + " ", end="")
    
            # If not visited, mark it as visited, and
            # enqueue it
            for neighbour in graph[vertex]:
                if neighbour not in visited:
                    visited.add(neighbour)
                    queue.append(neighbour)
    
    
    
    graph = {'0': set(['1', '2']),
              '1': set(['0', '3', '4']),
              '2': set(['0']),
              '3': set(['1']),
              '4': set(['2', '3'])}
             
    print("BFS Traversal: ")
    bfs(graph, '3')
    

  3. Breadth First Search code output:


  4. OUT: BFS Traversal:
    3 1 0 4 2





See also related topics: