Hitta en nod i en graf med BFS

I den här övningen ska du modifiera BFS-algoritmen för att söka efter en given nod i en graf.

För att hjälpa dig testa din kod har följande graf laddats in med hjälp av en ordbok.

Grafisk representation av en graf.

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

Den här övningen är en del av kursen

Datastrukturer och algoritmer i Python

Visa kurs

Övningsinstruktioner

Kontrollera om du hittat sökvärdet.
Returnera True om du hittat sökvärdet.
Kontrollera inuti for-loopen om den angränsande noden har besökts.
Returnera False om du inte hittat sökvärdet.

Interaktiv övning med praktiskt arbete

Testa den här övningen genom att slutföra den här exempelkoden.

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

Redigera och kör kod