有向图DFS/BFS实现问题：节点输出错误及图字典使用咨询

一、为什么输出了错误的节点？ #

你代码里的核心问题出在add_edge函数上——它默认把边处理成无向边了！看这段关键代码：

def add_edge(edge):
    u, v = edge
    if (v not in n_nodes[u]) and (u not in n_nodes[v]):
        n_nodes[u].append(v)
        if (u != v):
            n_nodes[v].append(u)

每次调用add_edge((u, v))时，不仅会把v添加到u的邻接列表，还会把u添加到v的邻接列表。但你要实现的是有向图，边是单向的（比如1→2不代表2→1），这个双向添加的逻辑完全不符合预期，导致每个节点的邻接列表都多了反向节点，才出现了错误输出。

举个具体例子：调用add_edge((1,2))时，代码会同时给n_nodes[1]加2、给n_nodes[2]加1，但预期里2的邻接节点并没有1，这就是实际结果和预期不符的根源。

二、如何直接使用给定的graph字典？ #

完全不需要逐条定义边，给定的graph字典本身就是现成的有向图邻接表结构，直接拿来用就行！修正后的代码会简洁很多：

graph = {'1': ['2','4'], '2': ['3', '5', '7'], '3': ['1','6'], '4': ['6'], '5': ['7','8'], '6': ['8'], '7': ['8', '9'], '8': ['9']}

# 直接遍历排序后的键，打印结果
for key in sorted(graph):
    print(f"{key} --> Node(s): {graph[key]}")

运行这段代码就能得到你想要的预期结果。如果担心修改原字典会有问题，也可以先做个浅拷贝：n_nodes = graph.copy()，再用n_nodes遍历打印，效果完全一致。

要是你还想保留自己的函数结构，只需要修改add_edge函数，去掉反向添加的逻辑即可：

def add_edge(edge):
    u, v = edge
    if v not in n_nodes[u]:
        n_nodes[u].append(v)

这样每条边就只会单向添加，符合有向图的要求了。

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