DEV Community

Cover image for Breadth First Search (BFS) Algorithm
Aya Bouchiha
Aya Bouchiha

Posted on

Breadth First Search (BFS) Algorithm

hi guys, on this beautiful day we'll talk about Breadth-First Search

Definition of Breadth-First Search Algorithm (BFS)

Breadth-First Search: is an algorithm that traverses and searches in trees and graphs using recursion and queue data structure, this algorithm comes to avoid processing a node more than once.

Time complexity and Space complexity of BFS

Space complexlity O(V)
Time complexity O(V+E)

Breadth-First Search applications

  • Google maps
  • Cheney's algorithm
  • Search Engines
  • Peer to Peer Networking
  • Ford-Fulkerson algorithm

Breadth-First Search approach

  • Initialize a queue

  • Mark the node as visited by inserting it to a list

  • Insert the vertices into the queue

  • While len(queue) > 0:

    • Delete the first item of the queue
    • mark as visited and push all adjacents unvisited nodes of the deleted Item.

Breadth-First Search implementation in python

more details...

If you are not familiar with python, I recommend you check this series

# CODE FROM https://favtutor.com/blogs/breadth-first-search-python

graph = {
  '5' : ['3','7'],
  '3' : ['2', '4'],
  '7' : ['8'],
  '2' : [],
  '4' : ['8'],
  '8' : []
}

visitedNodes = [] 
queue = []   

def bfs(visitedList: list, graph: dict, node):
    visitedList.append(node)
    queue.append(node)

    while queue:        
        m = queue.pop(0) 
        print (m, end = "\t") 
        for adjacent in graph[m]:
            if adjacent not in visitedList:
                visitedList.append(adjacent)
                queue.append(adjacent)

bfs(visitedNodes, graph, '5') # 5 3 7 2 4 8

Enter fullscreen mode Exit fullscreen mode

References and useful resources

Have a nice day!!

Top comments (0)