Get startedGet started for free

Finding a graph vertex using BFS

In this exercise, you will modify the BFS algorithm to search for a given vertex within a graph.

To help you test your code, the following graph has been loaded using a dictionary.

Graphical representation of a graph.

graph = {
  '4' : ['6','7'],
  '6' : ['4', '7', '8'],
  '7' : ['4', '6', '9'],
  '8' : ['6', '9'],
  '9' : ['7', '8']
}

This exercise is part of the course

Data Structures and Algorithms in Python

View Course

Exercise instructions

  • Check if you found the search value.
  • Return True if you found the search value.
  • Inside the for loop, check if the adjacent vertex has been visited.
  • Return False if you didn't find the search value.

Hands-on interactive exercise

Have a go at this exercise by completing this sample code.

import queue

def bfs(graph, initial_vertex, search_value):
  visited_vertices = []
  bfs_queue = queue.SimpleQueue()
  visited_vertices.append(initial_vertex)
  bfs_queue.put(initial_vertex)

  while not bfs_queue.empty():
    current_vertex = bfs_queue.get()
    # Check if you found the search value
    if ____:
      # Return True if you find the search value
      ____    
    for adjacent_vertex in graph[current_vertex]:
      # Check if the adjacent vertex has been visited
      if adjacent_vertex not in ____:
        visited_vertices.append(adjacent_vertex)
        bfs_queue.put(adjacent_vertex)
  # Return False if you didn't find the search value
  ____

print(bfs(graph, '4', '8'))
Edit and Run Code