使用字典(键为节点值为前驱)实现DFS时节点遍历不全的问题排查
DFS实现前驱记录逻辑错位、节点遍历不全问题
正在基于邻接表结构实现深度优先搜索,设计前驱记录字典的映射规则为:键是待访问的下一节点,对应的值为该节点的前驱节点。但当前代码运行后出现两个明显异常:
- 从指定起点出发的连通子图未被完整遍历,大量节点未出现在返回的前驱字典中
- 前驱映射关系完全不符合实际遍历路径的逻辑
现有实现代码
from collections import deque class Graph: def __init__(self, n): self.adj = {} for i in range(n): self.adj[i] = [] def are_connected(self, node1, node2): return node2 in self.adj[node1] def adjacent_nodes(self, node): return self.adj[node] def add_node(self): self.adj[len(self.adj)] = [] def add_edge(self, node1, node2): if node1 not in self.adj[node2]: self.adj[node1].append(node2) self.adj[node2].append(node1) def number_of_nodes(): return len() def DFS(G, node1): S = [node1] marked = {} pred = {} for node in G.adj: marked[node] = False while len(S) != 0: current_node = S.pop() if not marked[current_node]: marked[current_node] = True for node in G.adj[current_node]: S.append(node) if not marked[node]: pred[node] = current_node pred[current_node] = node return pred
复现代码
G = Graph(20) G.add_edge(1, 2) G.add_edge(2, 3) G.add_edge(3, 4) G.add_edge(0, 1) G.add_edge(4, 5) G.add_edge(5, 6) G.add_edge(6, 7) G.add_edge(4, 6) G.add_edge(2, 6) G.add_edge(8, 9) G.add_edge(10, 3) G.add_edge(2, 3) print(DFS(G, 1))
非预期运行结果
{0: 1, 6: 2, 10: 3, 1: 6}
核心错误定位
- 前驱赋值逻辑完全错位:原代码把给
pred字典赋值的语句写在了邻接表遍历的循环外面,此时代码用到的node变量是上一轮邻接遍历的最后一个值,既不是当前栈弹出的节点,也不是待入栈的邻接节点,判断条件和赋值对象全部错位。 - 遍历和前驱记录的逻辑割裂:DFS的栈遍历流程本身可以完成栈弹出、节点标记的动作,但本该在邻接节点第一次被压入栈时,同步记录“该邻接节点的前驱是当前弹出的节点”的逻辑没有写在对应位置,导致绝大多数遍历过的节点都没有被记录到前驱字典里。
- 残留变量的无意义赋值:循环最后单独写的
pred[current_node] = node用的是流程结束后的残留变量值,和实际遍历路径无关,会产生完全错误的映射关系。 - 图类方法存在隐藏语法错误:
number_of_nodes方法缺失实例参数self,且len()调用没有传入统计目标,后续调用会直接报错。
修正后的可运行实现
调整pred赋值的位置到邻接节点入栈的逻辑块内,保证每个邻接节点第一次被访问时,正确绑定和当前节点的前驱关系:
def DFS(G, node1): S = [node1] marked = {} pred = {} # 初始化起点的前驱为None pred[node1] = None for node in G.adj: marked[node] = False while len(S) != 0: current_node = S.pop() if not marked[current_node]: marked[current_node] = True # 遍历当前节点的所有邻接节点 for node in G.adj[current_node]: # 邻接节点未被标记时,记录前驱关系并入栈 if not marked[node]: pred[node] = current_node S.append(node) return pred
修正后从节点1出发调用DFS,会完整记录所有和1连通的节点(0、2、3、4、5、6、7、10)的前驱关系,不会出现遍历不全的问题。
内容的提问来源于stack exchange,提问作者dejsdukes
相关产品推荐
相关产品推荐

