ค้นหา vertex ในกราฟด้วย BFS

ในแบบฝึกหัดนี้ คุณจะปรับแก้อัลกอริทึม BFS เพื่อค้นหา vertex ที่ต้องการภายในกราฟ

กราฟต่อไปนี้ถูกโหลดไว้แล้วในรูปแบบ dictionary เพื่อใช้ทดสอบโค้ด

Graphical representation of a graph.

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

แบบฝึกหัดนี้เป็นส่วนหนึ่งของหลักสูตร

โครงสร้างข้อมูลและอัลกอริทึมใน Python

ดูคอร์ส

คำแนะนำการฝึกหัด

ตรวจสอบว่าพบค่าที่ค้นหาแล้วหรือไม่
คืนค่า True หากพบค่าที่ค้นหา
ภายใน for loop ให้ตรวจสอบว่า adjacent vertex ถูกเยี่ยมชมแล้วหรือยัง
คืนค่า False หากไม่พบค่าที่ค้นหา

แบบฝึกหัดเชิงโต้ตอบแบบลงมือทำ

ลองทำแบบฝึกหัดนี้โดยเติมโค้ดตัวอย่างนี้ให้สมบูรณ์

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

แก้ไขและรันโค้ด