Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

bfs
python

How to implement a ​breadth-first search in Python

Educative Answers Team

Breadth-first search (BFS) is an algorithm used for tree traversal on graphs or tree data structures. BFS can be easily implemented using recursion and data structures like dictionaries and lists.

The Algorithm

  1. Pick any node, visit the adjacent unvisited vertex, mark it as visited, display it, and insert it in a queue.
  2. If there are no remaining adjacent vertices left, remove the first vertex from the queue.
  3. Repeat step 1 and step 2 until the queue is empty or the desired node is found.

Implementation

Consider the​ graph, which ​is implemented in the code below:

svg viewer
graph = {
  'A' : ['B','C'],
  'B' : ['D', 'E'],
  'C' : ['F'],
  'D' : [],
  'E' : ['F'],
  'F' : []
}

visited = [] # List to keep track of visited nodes.
queue = []     #Initialize a queue

def bfs(visited, graph, node):
  visited.append(node)
  queue.append(node)

  while queue:
    s = queue.pop(0) 
    print (s, end = " ") 

    for neighbour in graph[s]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

# Driver Code
bfs(visited, graph, 'A')

Explanation

  • Lines 3-10: The illustrated graph is represented using an adjacency list. An easy way to do this in Python is to use a dictionary data structure, where each vertex has a stored list of its adjacent nodes.

  • Line 12: visited is a list that is used to keep track of visited nodes.

  • Line 13: queue is a list that is used to keep track of nodes currently in the queue.

  • Line 29: The arguments of the bfs function are the visited list, the graph in the form of a dictionary, and the starting node A.

  • Lines 15-26: bfs follows the algorithm described above:

    1. It checks and appends the starting node to the visited list and the queue.
    2. Then, while the queue contains elements, it keeps taking out nodes from the queue, appends the neighbors of that node to the queue if they are unvisited, and marks them as visited.
    3. This continues until the queue is empty.

Time Complexity

Since all of ​the nodes and vertices are visited, the time complexity for BFS on a graph is O(V+E)O(V + E); where VV is the number of vertices and EE is the number of edges.

RELATED TAGS

bfs
python
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring