Menemukan simpul graf menggunakan BFS

Dalam latihan ini, Anda akan memodifikasi algoritme BFS untuk mencari simpul tertentu di dalam sebuah graf.

Untuk membantu Anda menguji kode, graf berikut telah dimuat menggunakan dictionary.

Graphical representation of a graph.

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

Latihan ini adalah bagian dari kursus

Struktur Data dan Algoritma di Python

Lihat Kursus

Petunjuk latihan

Periksa apakah Anda telah menemukan nilai yang dicari.
Kembalikan True jika Anda menemukan nilai yang dicari.
Di dalam loop for, periksa apakah simpul bertetangga sudah dikunjungi.
Kembalikan False jika Anda tidak menemukan nilai yang dicari.

Latihan interaktif praktis

Cobalah latihan ini dengan menyelesaikan kode contoh berikut.

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

Edit dan Jalankan Kode