Găsirea unui vârf într-un graf folosind BFS

În acest exercițiu, vei modifica algoritmul BFS pentru a căuta un anumit vârf într-un graf.

Pentru a-ți testa codul, următorul graf a fost încărcat folosind un dicționar.

Reprezentare grafică a unui graf.

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

Acest exercițiu face parte din cursul

Structuri de date și algoritmi în Python

Vezi cursul

Instrucțiuni pentru exercițiu

Verifică dacă ai găsit valoarea căutată.
Returnează True dacă ai găsit valoarea căutată.
În interiorul buclei for, verifică dacă vârful adiacent a fost vizitat.
Returnează False dacă nu ai găsit valoarea căutată.

Exercițiu interactiv practic

Încearcă acest exercițiu completând acest cod de exemplu.

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

Editează și rulează codul