Поиск вершины графа с помощью BFS

В этом упражнении вы модифицируете алгоритм BFS, чтобы найти заданную вершину в графе.

Для тестирования кода загружен следующий граф, представленный в виде словаря.

Graphical representation of a graph.

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

Это упражнение является частью курса

Структуры данных и алгоритмы на Python

Посмотреть курс

Инструкции к упражнению

Проверьте, найдено ли искомое значение.
Верните True, если искомое значение найдено.
Внутри цикла for проверьте, была ли посещена смежная вершина.
Верните False, если искомое значение не найдено.

Интерактивное практическое упражнение

Попробуйте выполнить это упражнение, дополнив этот пример кода.

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'))

Редактировать и запускать код