Een knoop in een graaf vinden met BFS

In deze oefening ga je het BFS-algoritme aanpassen om naar een opgegeven knoop in een graaf te zoeken.

Om je code te testen is de volgende graaf geladen met behulp van een dictionary.

Graphical representation of a graph.

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

Deze oefening maakt deel uit van de cursus

Datastructuren en algoritmen in Python

Cursus bekijken

Oefeninstructies

Controleer of je de gezochte waarde hebt gevonden.
Geef True terug als je de gezochte waarde hebt gevonden.
Controleer binnen de for-lus of de aangrenzende knoop is bezocht.
Geef False terug als je de gezochte waarde niet hebt gevonden.

Praktische interactieve oefening

Probeer deze oefening eens door deze voorbeeldcode in te vullen.

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 bewerken en uitvoeren