Топологическая сортировка не ведет себя так, как ожидалось

Question

Вот моя реализация графика в 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 (п) ничего не получает добавленным и хотя рекурсия разворачиванию стек вызовов не переходит к следующей итерации пересечения соседей внутри top_sort_util. Не может показаться, что здесь логически неверно. Любая помощь приветствуется.

Answer 1

Если v.neighbors пуст, n никогда не устанавливается, поэтому stack.append(n)внеfor n in v.neighbors: терпит неудачу.

Если все n должны быть добавлены в стек (а не только последний), отступ stack.append() правильно, чтобы быть внутри цикла:

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)