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)

🔠 Find your favorite font

 
You can change your default font in Settings.