0
這是我在Python中的圖形實現。這是一個有向圖。拓撲排序不像預期的那樣運行
class DiGraph:
def __init__(self):
self.all_vertices = []
self.vertex_map = {}
self.size = 0
def add(self, a, b):
if a in self.vertex_map:
av = self.vertex_map[a]
if b in self.vertex_map:
bv = self.vertex_map[b]
av.add(bv)
else:
bv = Vertex(b)
av.add(bv)
self.vertex_map[b] = bv
self.all_vertices.append(bv)
self.size += 1
else:
av = Vertex(a)
self.size += 1
if b in self.vertex_map:
bv = self.vertex_map[b]
av.add(bv)
else:
bv = Vertex(b)
av.add(bv)
self.vertex_map[b] = bv
self.all_vertices.append(bv)
self.size += 1
self.vertex_map[a] = av
self.all_vertices.append(av)
def __sizeof__(self):
return self.size
def print(self):
for v in self.all_vertices:
print(v.data, end='->')
for n in v.neighbors:
print(n.data, end=', ')
print()
class Vertex:
def __init__(self, data):
self.data = data
self.neighbors = []
self.connections = 0
def add(self, item):
self.neighbors.append(item)
self.connections += 1
這是我的拓撲排序
def top_sort(g):
stack = []
visited = set()
for v in g.all_vertices:
if v not in visited:
top_sort_util(v, visited, stack)
for ele in stack:
print(ele, end=' ')
print()
def top_sort_util(v, visited, stack):
visited.add(v)
for n in v.neighbors:
if n in visited:
continue
top_sort_util(n, visited, stack)
stack.append(n)
這是主叫圖形代碼。
def main():
graph = DiGraph()
graph.add(1, 2)
graph.add(1, 3)
graph.add(3, 4)
graph.add(3, 5)
graph.add(2, 6)
graph.add(2, 7)
graph.add(2, 8)
top_sort(graph)
if __name__ == '__main__':
main()
這是錯誤信息，我得到的，
stack.append(n)
UnboundLocalError: local variable 'n' referenced before assignment
在調試代碼中，我可以看到，上線stack.append（N）沒有獲取附加儘管遞歸鋪開的調用堆棧不會進入遍歷top_sort_util內的鄰居的下一次迭代。 似乎無法理解這裏的邏輯不正確。 任何幫助表示讚賞。