在圖上實作 DFS
在此練習中，你要實作一個用來遍歷圖形的深度優先搜尋（DFS）演算法。
回顧步驟：
- 從任一頂點開始
- 將該頂點加入已造訪頂點的清單
- 對於目前節點的每個相鄰頂點
- 如果已造訪 -> 忽略
- 如果未造訪 -> 以遞迴方式執行 DFS
為了幫助你測試程式碼，下方的圖已用字典載入。
graph = {
'0' : ['1','2'],
'1' : ['0', '2', '3'],
'2' : ['0', '1', '4'],
'3' : ['1', '4'],
'4' : ['2', '3']
}
本練習屬於課程
Data Structures and Algorithms in Python
練習說明
- 檢查
current_vertex是否尚未被造訪。 - 將
current_vertex加入visited_vertices。 - 以適當的值傳入，遞迴呼叫
dfs()。
動手互動練習
試著完成這個範例程式碼，體驗一下這個練習。
def dfs(visited_vertices, graph, current_vertex):
# Check if current_vertex hasn't been visited yet
if current_vertex not in ____:
print(current_vertex)
# Add current_vertex to visited_vertices
____.add(____)
for adjacent_vertex in graph[current_vertex]:
# Call recursively with the appropriate values
____(____, ____, ____)
dfs(set(), graph, '0')