Trovare un vertice del grafo usando BFS

In questo esercizio, modificherai l'algoritmo BFS per cercare un determinato vertice all'interno di un grafo.

Per aiutarti a testare il tuo codice, il seguente grafo è stato caricato usando un dizionario.

Graphical representation of a graph.

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

Questo esercizio fa parte del corso

Strutture dati e algoritmi in Python

Visualizza il corso

Istruzioni dell'esercizio

Verifica se hai trovato il valore da cercare.
Restituisci True se hai trovato il valore da cercare.
All'interno del ciclo for, controlla se il vertice adiacente è già stato visitato.
Restituisci False se non hai trovato il valore da cercare.

Esercizio pratico interattivo

Prova a risolvere questo esercizio completando il codice di esempio.

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

Modifica ed esegui il codice