Python实现Graph类拓扑排序功能运行时报错,求排查修复方案
报错原因
- 缺少依赖导入:代码使用了
defaultdict数据结构,但没有提前从collections模块导入,会触发NameError - 类方法缩进错误:
topogologicalSortUtil、topologicalSort两个方法没有缩进归入Graph类的作用域,不属于类的成员方法,调用时会触发AttributeError;同时两个方法内部的首行代码也存在缩进错误,不属于方法体范畴,会直接触发语法错误。 - (可选非阻断问题)方法名拼写存在笔误,
topogologicalSortUtil多写了一个字母o,只要定义和调用时拼写一致就不会影响运行,可按需修正。
修复方案
- 代码开头增加导入语句
from collections import defaultdict - 调整缩进层级,把两个拓扑排序相关方法归入
Graph类内部,同时修正方法内部代码的缩进。
修复后完整可运行代码
from collections import defaultdict # 初始化图类 class Graph: def __init__(self, numberofVertices): self.graph = defaultdict(list) self.numberofVertices = numberofVertices def addEdge(self, vertex, edge): self.graph[vertex].append(edge) # 实现拓扑排序 def topogologicalSortUtil(self, v, visited, stack): visited.append(v) for i in self.graph[v]: if i not in visited: self.topogologicalSortUtil(i, visited, stack) stack.insert(0, v) def topologicalSort(self): visited = [] stack = [] for k in list(self.graph): if k not in visited: self.topogologicalSortUtil(k, visited, stack) print(stack) tempGraph = Graph(8) tempGraph.addEdge("A", "C") tempGraph.addEdge("C", "E") tempGraph.addEdge("E", "H") tempGraph.addEdge("E", "F") tempGraph.addEdge("F", "G") tempGraph.addEdge("B", "D") tempGraph.addEdge("B", "C") tempGraph.addEdge("D", "F") tempGraph.topologicalSort()
运行后会输出合法的拓扑排序结果,例如['B', 'D', 'A', 'C', 'E', 'F', 'G', 'H'](拓扑排序结果不唯一,只要满足依赖顺序均为正确结果)。
内容的提问来源于stack exchange,提问作者Habib Ur Rehman
相关产品推荐
相关产品推荐

