深度优先算法

Depth First Search，一种优先走到底、无路可走再回头的遍历方式。

深度优先遍历的序列不唯一。相邻节点的遍历顺序允许被任意打乱。

测试图的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
graph1:
    A
   / \
  B   C
 / \   \
D   E   F
     \
      F

graph2:
	0
   / \
  1   3
 / \ / \
2   4   6
 \ / \ /
  5   7
   \ /
	8

实践

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from collections import deque

def dfs(graph, start):
    # 初始化一个集合，用于存储已经访问过的节点
    # 使用集合是为了快速查找节点是否已经被访问过，避免重复访问
    visited = set()
    
    # 初始化栈，将起始节点加入栈中
    # 栈用于存储待访问的节点。栈的特性是后进先出（LIFO），即会先访问最近加入的节点
    stack = [start]
    
    # 初始化一个列表，用于记录节点的遍历顺序
    # 该列表将用于保存遍历的顺序，最终返回的就是这个顺序
    traversal_order = []
    
    # 开始 DFS 循环，当栈非空时继续
    # 栈中始终保存着待访问的节点，每次循环访问栈顶的节点
    while stack:
        # 从栈顶弹出一个节点
        # 弹出栈顶节点，即最先进入栈的节点，这个节点是当前要访问的节点
        node = stack.pop()
        
        # 如果当前节点尚未访问
        # 检查当前节点是否已经被访问过
        if node not in visited:
            # 将当前节点标记为已访问，加入到 visited 集合
            # 将节点标记为已访问，防止之后重复访问
            visited.add(node)
            
            # 将当前节点记录到遍历顺序中
            # 访问节点后，将其加入遍历顺序中
            traversal_order.append(node)
            
            # 将当前节点的邻居节点加入栈中
            # 对当前节点的每一个邻居进行处理，只有未访问过的邻居才加入栈
            # 这里是将邻居节点逆序压入栈中，以确保访问顺序正确（栈是后进先出的）
            # 使用生成器表达式高效地筛选出未访问的邻居
            stack.extend(
                neighbor for neighbor in reversed(graph[node]) if neighbor not in visited
            )
    
    # 返回记录的遍历顺序
    # 当栈为空时，表示所有可达的节点都已经访问过，返回遍历顺序
    return traversal_order

# 测试
search.test(dfs)

流程图

graph TD
    Start["Start: Initialize visited, stack, and traversal_order"] --> A["Push the starting node onto stack"]
    A --> B["Check if stack is empty"]
    B -->|Stack is not empty| C["Pop the node from stack"]
    C --> D["Check if the node is in visited"]
    D -->|Not visited| E["Mark the node as visited"]
    E --> F["Append the node to traversal_order"]
    F --> G["Get neighbors of the node from graph[node]"]
    G --> H["Filter neighbors: Keep only unvisited neighbors"]
    H --> I["Push unvisited neighbors onto stack"]
    I --> B
    D -->|Already visited| B
    B -->|Stack is empty| End["End: Return traversal_order"]

    %% Subprocess for processing neighbors
    subgraph Loop["Neighbor Processing Logic"]
        G --> J["Iterate through each neighbor in graph[node]"]
        J --> K["Check if neighbor is in visited"]
        K -->|Not visited| L["Push the neighbor onto stack"]
        K -->|Already visited| M["Skip the neighbor"]
        L --> H
        M --> J
end