Python中DFS算法实例变量call_count无法递增问题排查

问题根源 #

核心问题在于整数是不可变类型：

• 当你把call_count作为参数传递给递归函数时，传递的是当前值的副本。每次call_count +=1只是修改了当前函数栈中的局部变量，不会影响上层函数的call_count变量，更不会更新类的实例变量self.call_count。
• 对比final_path：列表是可变类型，传递的是对象引用，所以递归中对列表的修改（如append）会直接作用于原对象，因此能正常工作。

修复现有代码的两种方式 #

方式1：直接使用实例变量（最简洁） #

不需要把call_count作为参数传递，直接操作类的实例变量，所有递归调用共享同一个计数：

class Node:
    def __init__(self, id, connections):
        self.id = id
        self.connections = connections


class DFS:
    def __init__(self):
        self.visited = {}
        self.nodes = []
        self.final_path = []
        self.call_count = 0

    def searchDFS(self, nodes, target, current, final_path=None, visited=None):
        if visited is None:
            visited = self.visited
        if final_path is None:
            final_path = self.final_path
        
        self.call_count += 1  # 直接递增实例变量
        
        if current in visited: 
            print(f'already visited node {current}')
            return 0
             
        else:
            print(f'current -> {current}')
            visited[current] = 1

            if current == target: 
                print('found!')
                final_path.append(current)
                return True
            
            if nodes[current].connections:
                for node in nodes[current].connections:
                    if self.searchDFS(nodes, target, node.id, final_path, visited):
                        final_path.append(current)
                        if current == 0: 
                            print(final_path[::-1])
                            print(f'call count: {self.call_count}')  # 打印实例变量
                        return True
            return False

    # 其余方法（setup_graph、print_graph、main）保持不变

方式2：用可变对象包裹整数（保留参数传递逻辑） #

如果需要保留参数传递的方式，可以用单元素列表包裹整数（列表是可变类型，传递的是引用）：

class Node:
    def __init__(self, id, connections):
        self.id = id
        self.connections = connections


class DFS:
    def __init__(self):
        self.visited = {}
        self.nodes = []
        self.final_path = []
        self.call_count = 0

    def searchDFS(self, nodes, target, current, call_count=None, final_path=None, visited=None):
        if visited is None:
            visited = self.visited
        if final_path is None:
            final_path = self.final_path
        if call_count is None:
            call_count = [self.call_count]  # 用列表包裹整数
        
        call_count[0] += 1  # 修改列表内的元素，所有层级共享
        
        if current in visited: 
            print(f'already visited node {current}')
            return 0
             
        else:
            print(f'current -> {current}')
            visited[current] = 1

            if current == target: 
                print('found!')
                final_path.append(current)
                return True
            
            if nodes[current].connections:
                for node in nodes[current].connections:
                    if self.searchDFS(nodes, target, node.id, call_count, final_path, visited):
                        final_path.append(current)
                        if current == 0: 
                            print(final_path[::-1])
                            print(f'call count: {call_count[0]}')  # 读取列表内的值
                        return True
            return False

    # 其余方法保持不变

更优的实现方式：无状态封装的DFS #

把DFS的状态（访问记录、路径、调用次数）封装在函数内部，避免依赖类实例变量，让逻辑更独立、易于复用：

class Node:
    def __init__(self, id, connections):
        self.id = id
        self.connections = connections

def dfs_search(nodes, start, target):
    visited = set()
    final_path = []
    call_count = 0

    def dfs(current):
        nonlocal call_count
        call_count += 1

        if current in visited:
            print(f'already visited node {current}')
            return False
        visited.add(current)
        print(f'current -> {current}')

        if current == target:
            print('found!')
            final_path.append(current)
            return True
        
        for node in nodes[current].connections:
            if dfs(node.id):
                final_path.append(current)
                return True
        return False

    dfs(start)
    if final_path:
        print(f'Path: {final_path[::-1]}')
    print(f'Total call count: {call_count}')
    return final_path[::-1] if final_path else None

# 测试代码
def setup_graph():
    nodes = []
    for x in range(5):
        nodes.append(Node(x, []))
    nodes[0].connections = [nodes[1], nodes[2]]
    nodes[1].connections = [nodes[0], nodes[3]]
    nodes[2].connections = [nodes[0], nodes[4]]
    nodes[3].connections = [nodes[1]]
    nodes[4].connections = [nodes[2]]
    return nodes

if __name__ == "__main__":
    print('init')
    graph_nodes = setup_graph()
    # 打印图结构
    for node in graph_nodes:
        print(f"node id: {node.id}")
        print("children: ")
        for child in node.connections:
            print(child.id)
    dfs_search(graph_nodes, 0, 4)

这个实现的优势：

• 用nonlocal关键字管理嵌套函数的状态，避免类实例变量的依赖。
• 使用set存储访问节点，比字典更简洁高效。
• 核心逻辑封装在内部函数，对外暴露简洁的调用接口。

内容的提问来源于stack exchange，提问作者ring0-collections