Hledání vrcholu grafu pomocí BFS

V tomto cvičení upravíš algoritmus BFS tak, aby vyhledal daný vrchol v grafu.

Aby sis mohl/a kód otestovat, byl načten následující graf pomocí slovníku.

Grafické znázornění grafu.

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

Toto cvičení je součástí kurzu

Datové struktury a algoritmy v Pythonu

Zobrazit kurz

Pokyny k cvičení

Zkontroluj, jestli jsi našel/a hledanou hodnotu.
Pokud jsi hledanou hodnotu našel/a, vrať True.
Uvnitř smyčky for ověř, jestli byl sousední vrchol už navštíven.
Pokud jsi hledanou hodnotu nenašel/a, vrať False.

Interaktivní cvičení na vyzkoušení si v praxi

Vyzkoušejte si toto cvičení dokončením tohoto ukázkového kódu.

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

Upravit a spustit kód