使用defaultdict构建邻接表的DFS代码为何输入构建时无法终止？

核心原因分析 #

1. 节点类型不匹配 #

硬编码邻接表时通常使用整数类型节点，但用户输入的节点默认是字符串类型。DFS遍历中，字符串节点（如"1"）和整数节点（如1）会被判定为不同节点，导致已访问集合无法正确标记，程序陷入无限递归。

2. 已访问集合未全局共享 #

若DFS函数内部每次递归都创建新的visited集合，而非传递同一个集合，会导致节点永远无法被标记为已访问，进而无限遍历。

3. 输入边重复添加（次要） #

输入处理逻辑未做去重时，同一双向边会被多次添加到邻接表，虽然不会直接导致无限循环，但会增加不必要的递归次数，极端情况下可能触发栈溢出。

针对性解决方案 #

1. 统一节点数据类型 #

将输入的节点字符串强制转换为整数（或与硬编码一致的类型）：

from collections import defaultdict

def build_graph_from_input():
    graph = defaultdict(list)
    edge_count = int(input("输入边的数量: "))
    for _ in range(edge_count):
        # 直接将输入转为整数
        u, v = map(int, input("输入两个节点（空格分隔）: ").split())
        graph[u].append(v)
        graph[v].append(u)
    return graph

2. 共享已访问集合 #

在DFS函数外部初始化visited集合，并通过参数传递给递归调用：

def dfs(current_node, graph, visited):
    if current_node in visited:
        return
    # 标记当前节点为已访问
    visited.add(current_node)
    print(current_node, end=" ")
    # 遍历所有邻居
    for neighbor in graph[current_node]:
        dfs(neighbor, graph, visited)

# 调用示例
if __name__ == "__main__":
    input_graph = build_graph_from_input()
    visited_nodes = set()
    # 从节点1开始遍历（可根据需求修改起始节点）
    dfs(1, input_graph, visited_nodes)

3. 可选：输入边去重优化 #

使用set存储邻居节点自动去重，避免邻接表中出现重复条目：

def build_graph_from_input():
    graph = defaultdict(set)
    edge_count = int(input("输入边的数量: "))
    for _ in range(edge_count):
        u, v = map(int, input("输入两个节点（空格分隔）: ").split())
        graph[u].add(v)
        graph[v].add(u)
    # 转换为list保持和硬编码邻接表格式一致
    for node in graph:
        graph[node] = list(graph[node])
    return graph

错误代码示例（供对比） #

如果你的DFS函数是这样写的，必然会无限循环：

# 错误：每次递归新建visited集合，无法标记已访问节点
def bad_dfs(node, graph):
    visited = set()
    if node in visited:
        return
    visited.add(node)
    print(node, end=" ")
    for neighbor in graph[node]:
        bad_dfs(neighbor, graph)

内容的提问来源于stack exchange，提问作者Rohan Nag