在图上实现 DFS
在本练习中，您将实现一种用于遍历图的 深度优先搜索（DFS）算法。
回顾步骤：
- 从任意顶点开始
- 将该顶点加入已访问顶点列表
- 对于当前节点的每个相邻顶点
- 若已访问 -> 忽略
- 若未访问 -> 递归执行 DFS
为便于您测试代码，下面的图已使用字典加载。
graph = {
'0' : ['1','2'],
'1' : ['0', '2', '3'],
'2' : ['0', '1', '4'],
'3' : ['1', '4'],
'4' : ['2', '3']
}
本练习是课程的一部分
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')