Python BFS遍历图代码异常求助：从节点3统计访问顶点数结果不符

我编写了一段Python代码，从指定节点3出发对图进行BFS遍历，目标是输出访问到的顶点总数，但代码运行结果异常。比如针对以下输入，正确输出应为6，但我的代码仅输出3。

输入示例 #

6
1 2
1 3
2 4
3 5
3 6
4 6

问题代码 #

from collections import defaultdict

def make_graph(graph,u,v):
    graph[u].append(v)
def bfs(visited, graph, node):
    output=[]
    visited.append(node)
    queue.append(node)
    while queue:
        node = queue.pop(0)
        output.append(node)
        for nghbr in graph[node]:
            if nghbr not in visited:
                visited.append( nghbr )
                queue.append( nghbr )
    print(len(output))

x='3'
#bfs starts from node x in graph
n=int(input())
#n:number of nodes(number of nodes is equal to number of edges)
graph = defaultdict(list)
visited=[]
queue = []
for i in range (n):
    u,v=input().split()
    make_graph(graph,u,v)

bfs(visited, graph,x)

错误原因与修复方案 #

1. 无向图仅存储单向边 #

输入的图是无向图，但make_graph函数只将v添加到u的邻接表中，未反向添加u到v的邻接表。比如输入1 3时，仅记录了1的邻居是3，但没记录3的邻居是1，导致从节点3出发无法访问到1、2、4这些节点。
修复方法：修改make_graph函数，双向添加边：

def make_graph(graph,u,v):
    graph[u].append(v)
    graph[v].append(u)

2. 代码逻辑优化建议 #

• 用set存储visited：列表的in操作时间复杂度为O(n)，而集合是O(1)，能提升查找效率。
• 避免全局队列：将队列放在BFS函数内部初始化，防止多次调用时的状态污染。
• 使用deque替代列表做队列：deque.popleft()的时间复杂度是O(1)，比list.pop(0)的O(n)效率更高。

修复后的完整代码 #

from collections import defaultdict, deque

def make_graph(graph, u, v):
    graph[u].append(v)
    graph[v].append(u)

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    visited.add(start_node)
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    print(count)

x = '3'
edge_count = int(input())
graph = defaultdict(list)
for _ in range(edge_count):
    u, v = input().split()
    make_graph(graph, u, v)

bfs(graph, x)

运行上述修复后的代码，输入示例将输出正确结果6。

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