Пошук вершини графа за допомогою 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'))

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