深度优先搜索算法

深度优先搜索（DFS：Depth-First Search）是一种用于遍历或搜索树和图的算法。它的核心思想是尽可能深入地遍历结构，而不是广度优先搜索（BFS）那样按层级进行。

基本思想

1. 从起始节点开始访问。
2. 沿着当前路径不断深入，直到到达一个无法继续扩展的节点（通常是叶子节点或者死胡同）。
3. 回溯到上一个节点，尝试探索未访问的其他路径。
4. 这个过程持续进行，直到所有节点都被访问。

实现方法

递归实现

def dfs(graph, node, visited):
    if node not in visited: # 如果当前节点未被访问过
        print(node)  # 打印当前节点
        visited.add(node) # 并把当前节点添加到已访问的节点集合中
        for neighbor in graph[node]: # 对于当前节点相邻的每个节点都递归执行
            dfs(graph, neighbor, visited)
            
# 示例图
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

visited = set()
dfs(graph, 'A', visited)

# 输出结果：
A # 执行dfs(graph, 'A', visited)找到了两个子节点B和C
B # 先执行A的子节点列表中的第一个元素B，执行dfs(graph, 'B', visited)，找到B的两个子节点D和E
C # 再执行第二个元素C，执行dfs(graph, 'C', visited)，找到C的子节点F，此时dfs(graph, 'A', visited)结束
D # 先执行B子节点列表中第一个元素D，执行dfs(graph, 'D', visited)，由于D没有子节点，将D添加到visited后结束
E # 再执行第二个元素E，执行dfs(graph, 'E', visited)，找到E的子节点F
F # 这里是C触发的dfs(graph, 'F', visited)，E第二次触发后会由于F已经被访问不再打印

栈实现

栈是一种先进后出的数据结构，好比往一个盒子中放书，先放进去的书需要先拿出后放进去的书才能取出；而深度优先的核心就在于不断深入，利用栈的特点就可以先放入起始节点，然后弹出栈顶的节点并压入当前节点的子节点，为了保证深度优先需要反向压入。

def dfs_stack(graph, start):
    stack = [start] # 初始化栈，先放入起始节点
    visited = set() # 用一个集合来记录访问过的节点

    while stack: # 栈不为空时
        node = stack.pop() # 弹出栈顶元素，pop()方法移除并返回列表中最后一个元素
        if node not in visited: # 如果当前节点未被访问过
            print(node)  # 打印当前节点
            visited.add(node) # 并把当前节点添加到已访问的节点集合中
            stack.extend(reversed(graph[node]))  # 确保深度优先
			# graph[node]返回当前节点的子节点列表
			# reversed()方法将子节点列表进行反转，因为pop()返回的是列表最后一个元素
			# extend()方法将反转后的列表元素添加到栈中，重复执行while stack循环
			
# 还是这个图
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs_stack(graph, 'A')

# 输出结果：
A # 弹出A后stack = ['C', 'B']
B # 弹出B后stack = ['C', 'E', 'D']，因为graph['B']的值['D', 'E']被压入了栈
D # 弹出D后stack = ['C', 'E']，由于graph['D'] = []所以没有元素被压入栈
E # 弹出E后stack = ['C', 'F']，graph['E']的值['F']被压入栈
F # 弹出F后stack = ['C']，没有元素被压入栈
C # 弹出C后stack为空列表，while循环结束，dfs_stack()执行完毕

实例应用

# 节点依赖关系如下，其中I节点为起点，F节点为终点，找出所有路径
dependencies = { 
	'I1': ['N1', 'N5', 'N7'],
 	'I2': ['N2', 'N5', 'N7'], 
 	'I3': ['N3'], 
	 'I4': ['N4'], 
	 'N3': ['N7', 'N8'], 
	 'N4': ['N7', 'N8'], 
	 'N1': ['N7', 'N8'], 
	 'N2': ['N7', 'N8'], 
	 'N7': ['N6'], 
	 'N8': ['N6'], 
	 'N5': ['F1'], 
	 'N6': ['F1']
 }

def find_paths(current_node, path, dependencies, all_paths):
    path.append(current_node) # 传入的起始节点添加到路径列表中
    # 如果当前节点是终止节点（以 "F" 开头），结束递归并保存路径列表
    if current_node.startswith("F"):
        all_paths.append(path)
    else:
        # 遍历当前节点的所有依赖节点
        for next_node in dependencies.get(current_node, []):
            find_paths(next_node, path[:], dependencies, all_paths)  
            # 这里使用切片[:]是为了传递path的副本，避免递归过程中修改path影响其他分支

def find_all_paths(dependencies):
    all_paths = [] # 用一个列表来存储构建的路径
    start_nodes = [node for node in dependencies if node.startswith("I")]  # 获取一个存储起始节点的列表
    for start_node in start_nodes: # 对于每个起始节点，调用find_paths函数添加路径到all_paths中
        find_paths(start_node, [], dependencies, all_paths)
    return all_paths

paths = find_all_paths(dependencies) # 调用函数，获取所有路径
for path in paths: # 遍历所有路径
    print(path) # 打印每一条路径

# 输出结果
['I1', 'N1', 'N7', 'N6', 'F1']
['I1', 'N1', 'N8', 'N6', 'F1']
['I1', 'N5', 'F1']
['I1', 'N7', 'N6', 'F1']
['I2', 'N2', 'N7', 'N6', 'F1']
['I2', 'N2', 'N8', 'N6', 'F1']
['I2', 'N5', 'F1']
['I2', 'N7', 'N6', 'F1']
['I3', 'N3', 'N7', 'N6', 'F1']
['I3', 'N3', 'N8', 'N6', 'F1']
['I4', 'N4', 'N7', 'N6', 'F1']
['I4', 'N4', 'N8', 'N6', 'F1']