Einen Graphenvertex finden mit BFS

In dieser Übung modifizierst du den BFS Algorithmus, um nach einem bestimmten Knotenpunkt in einem Graphen zu suchen.

Damit du deinen Code testen kannst, wurde die folgende Grafik mit einem Wörterbuch geladen.

Grafische Darstellung eines Diagramms.

graph = {

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

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

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

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

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

}

Diese Übung ist Teil des Kurses

Datenstrukturen und Algorithmen in Python

Kurs anzeigen

Anleitung zur Übung

Prüfe, ob du den Suchwert gefunden hast.
Gib True zurück, wenn du den Suchwert gefunden hast.
Prüfe in der Schleife for, ob der benachbarte Eckpunkt besucht wurde.
Gib False zurück, wenn du den Suchwert nicht gefunden hast.

Interaktive Übung

Versuche dich an dieser Übung, indem du diesen Beispielcode vervollständigst.

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

Code bearbeiten und ausführen