Tìm một đỉnh trong đồ thị bằng BFS
Trong bài tập này, bạn sẽ chỉnh sửa thuật toán BFS để tìm một đỉnh cho trước trong đồ thị.
Để bạn dễ kiểm thử mã, đồ thị sau đã được nạp bằng một dictionary.
graph = {
'4' : ['6','7'],
'6' : ['4', '7', '8'],
'7' : ['4', '6', '9'],
'8' : ['6', '9'],
'9' : ['7', '8']
}
Bài tập này là một phần của khóa học
Cấu trúc dữ liệu và Thuật toán với Python
Hướng dẫn bài tập
- Kiểm tra xem bạn đã tìm thấy giá trị cần tìm hay chưa.
- Trả về
Truenếu bạn đã tìm thấy giá trị cần tìm. - Bên trong vòng lặp
for, kiểm tra xem đỉnh kề đã được thăm hay chưa. - Trả về
Falsenếu bạn không tìm thấy giá trị cần tìm.
Bài tập tương tác thực hành trực tiếp
Hãy thử làm bài tập này bằng cách hoàn thành đoạn mã mẫu này.
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'))