如何在Python中实现读取文本文件数据的广度优先搜索(BFS)

你当前的核心问题是文本输入的解析逻辑和实际输入格式不匹配：你存储输入的文本每行对应一条边的(起点u, 终点v)，但你写的convert函数是按照邻接矩阵的逻辑做转换，和输入格式完全不契合。

你已经实现的Graph类不需要做任何修改，只需要调整输入解析逻辑，直接把读取到的每行两个值作为边传入addEdge方法即可直接适配。

完整可运行代码 #

from collections import defaultdict

class Graph:
    def __init__(self): 
        self.graph = defaultdict(list) 
    def addEdge(self,u,v):
        self.graph[u].append(v)
    def BFS(self, s):
        visited = [False] * (max(self.graph) + 1)
        queue = []
        queue.append(s)
        visited[s] = True
        while queue:       
            s = queue.pop(0)
            print (s, end = " ")         
            for i in self.graph[s]:
                if visited[i] == False:
                    queue.append(i)
                    visited[i] = True

# 读取文本文件部分（优化为with语法自动管理文件资源）
list_of_lists = []
with open("ajd.txt", "r") as data:
    for line in data.readlines():
        stripped_line = line.strip('\n')
        line_list = list(map(int, stripped_line.split(',')))
        list_of_lists.append(line_list)

# 初始化图并批量添加边
g = Graph()
for u, v in list_of_lists:
    g.addEdge(u, v)

# 调用BFS，可自行修改起始节点
g.BFS(1)

可选优化 #

如果你后续使用的节点编号不连续、存在较大间隔，可以修改BFS的visited实现为字典，避免不必要的空间浪费：

def BFS(self, s):
    visited = {}
    queue = []
    queue.append(s)
    visited[s] = True
    while queue:       
        s = queue.pop(0)
        print (s, end = " ")         
        for i in self.graph[s]:
            if i not in visited:
                queue.append(i)
                visited[i] = True

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