You need to enable JavaScript to run this app. 使用字典(键为节点值为前驱)实现DFS时节点遍历不全的问题排查
优惠活动
大模型
产品
解决方案
定价
更多

使用字典(键为节点值为前驱)实现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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.30 19:24:09