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）にそれを見ることができます私が取得エラーメッセージ、コードのデバッグに
stack.append(n)
UnboundLocalError: local variable 'n' referenced before assignment
では何も追加されなかっ取得し、再帰が出て折るのにコールスタックは、top_sort_util内のネイバを横切る次の反復には向かない。 論理的にここで何が間違っているのか分からないようです。 助けていただければ幸いです。