使用 BFS 尋找圖形的節點
在這個練習中，你將會「修改」BFS 演算法，來「搜尋圖形中指定的節點」。
為了幫助你測試程式碼，以下的圖形已用字典載入。
graph = {
'4' : ['6','7'],
'6' : ['4', '7', '8'],
'7' : ['4', '6', '9'],
'8' : ['6', '9'],
'9' : ['7', '8']
}
本練習屬於課程
Data Structures and Algorithms in Python
練習說明
- 檢查是否找到搜尋值。
- 若找到搜尋值則回傳
True。 - 在
for迴圈內檢查相鄰節點是否已被拜訪。 - 若未找到搜尋值則回傳
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'))