Encontrar um vértice de gráfico usando BFS

Neste exercício, você modificará o algoritmo BFS para pesquisar um determinado vértice em um gráfico.

Para ajudar você a testar seu código, o gráfico a seguir foi carregado usando um dicionário.

Representação gráfica de um gráfico.

graph = {

  '4' : ['6','7'],

  '6' : ['4', '7', '8'],

  '7' : ['4', '6', '9'],

  '8' : ['6', '9'],

  '9' : ['7', '8']

}

Este exercício faz parte do curso

Estruturas de dados e algoritmos em Python

Ver Curso

Instruções de exercício

Verifique se você encontrou o valor da pesquisa.
Retorne True se você encontrou o valor da pesquisa.
Dentro do loop for, verifique se o vértice adjacente foi visitado.
Retorne False se você não encontrou o valor da pesquisa.

Exercício interativo prático

Experimente este exercício preenchendo este código de exemplo.

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

Editar e executar código