Búsqueda de un vértice de grafo mediante BFS

En este ejercicio, modificarás el algoritmo BFS para buscar un vértice dado dentro de un grafo.

Para ayudarte a probar tu código, se ha cargado el grafo indicado a continuación utilizando un diccionario.

Representación gráfica de un grafo.

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

Este ejercicio forma parte del curso

Estructuras de datos y algoritmos en Python

Ver curso

Instrucciones de ejercicio

Comprueba si has encontrado el valor de búsqueda.
Devuelve True si has encontrado el valor de búsqueda.
Dentro del bucle for, comprueba si se ha visitado el vértice adyacente.
Devuelve False si no has encontrado el valor de búsqueda.

Ejercicio interactivo práctico

Pruebe este ejercicio completando este código de muestra.

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 y ejecutar código