DFS中“explored”的含义？如何确定树中的已探索集合？

核心定义 #

Explored集合（已探索集合）是状态空间搜索算法（如BFS、DFS）中，记录已经被完全处理完毕的节点的集合。这里的“完全处理”指：该节点的所有子节点/相邻状态都已经被遍历过，符合条件的子节点也已被加入到待处理的Open（ frontier ）集合中。

它和Open集合的核心区别：

• Open集合：存放待访问、待处理的节点
• Explored集合：存放已经处理完成，不会再被重复访问的节点

结合你的场景（起始A，目标E）的判定流程 #

以两种常见搜索算法为例，看Explored集合的更新逻辑：

1. 广度优先搜索（BFS） #

• 初始状态：Open = [A]，Explored = []
• 第一步：取出A，检查不是目标E，将A的所有相邻节点（假设为B、C）加入Open集合，随后把A移入Explored → Open = [B,C]，Explored = [A]
• 第二步：取出B，检查不是E，将B的未在Open/Explored中的相邻节点加入Open，把B移入Explored → Open = [C, D]（假设B的邻居是D），Explored = [A,B]
• 重复上述步骤，直到取出目标节点E，或是Open集合为空

2. 深度优先搜索（DFS） #

• 初始状态：Open = [A]，Explored = []
• 第一步：取出A，检查不是E，先把A移入Explored，再将A的相邻节点逆序加入Open（DFS用栈结构，后进先出）→ Open = [C,B]，Explored = [A]
• 第二步：取出C，检查不是E，移入Explored，将C的未在Open/Explored中的相邻节点加入Open → Open = [B, E]（假设C的邻居是E），Explored = [A,C]
• 此时取出E，匹配目标，搜索结束

核心作用 #

• 避免节点被重复访问，防止搜索陷入循环（比如存在A→B→A的环时，没有Explored集合会无限循环）
• 明确区分节点的处理状态，保证搜索逻辑的正确性和效率

内容的提问来源于stack exchange，提问作者Nahian Sarower Siam