leetcode-DepthFirstSearch

DFS - 深度优先搜索

DFS的思考步骤

  1. 确认递归函数，参数
  2. 确认终止条件
  3. 处理目前搜索节点出发的路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def dfs(参数):
    if 终止条件:
        # 存放结果
        return

    for 选择 in 当前节点的邻居:  # 本节点所连接的其他节点
        # 处理节点
        dfs(选择)  # 递归调用
        # 回溯，撤销处理结果
        
       
def dfs(parameters):
    if termination_condition:
        store_result()
        return

    for choice in connected_nodes_of_current_node:
        process_node(choice)
        dfs(graph, chosen_node)  # Recursion
        undo_process_node(choice)  # Backtrack