Я изучал топологическую сортировку и наткнулся на код Python GeeksforGeek.

 # Python program to print topological sorting of a DAG 
from collections import defaultdict 
  
# Class to represent a graph 
class Graph: 
    def __init__(self,vertices): 
        self.graph = defaultdict(list) # dictionary containing adjacency List 
        self.V = vertices #No. of vertices 
  
    # function to add an edge to graph 
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
  
    # A recursive function used by topologicalSort 
    def topologicalSortUtil(self,v,visited,stack): 
  
        # Mark the current node as visited. 
        visited[v] = True
  
        # Recur for all the vertices adjacent to this vertex 
        for i in self.graph[v]: 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        # Push current vertex to stack which stores result 
        stack.insert(0,v) 
  
    # The function to do Topological Sort. It uses recursive  
    # topologicalSortUtil() 
    def topologicalSort(self): 
        # Mark all the vertices as not visited 
        visited = [False]*self.V 
        stack =[] 
  
        # Call the recursive helper function to store Topological 
        # Sort starting from all vertices one by one 
        for i in range(self.V): 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        # Print contents of stack 
        print stack 

# Driver Code
g = Graph(6) 
g.addEdge(5, 2)
g.addEdge(5, 0) 
g.addEdge(4, 0) 
g.addEdge(4, 1) 
g.addEdge(2, 3) 
g.addEdge(3, 1) 
  
print "Following is a Topological Sort of the given graph"
g.topologicalSort() 
  

Однако я изменил входные данные, потому что хотел протестировать реальный случай, который мне нужен для моего проекта.

 g = Graph(5) 

g.addEdge(1, 2); 
g.addEdge(2, 3); 
g.addEdge(3, 4); 
g.addEdge(4, 5); 
  

Но я получаю исключение «индекс списка вне диапазона» в рекуррентной функции и не могу понять, почему.

Трассировка стека

 IndexError                                Traceback (most recent call last)
<ipython-input-8-cb05f6defc6c> in <module>
     54 
     55 print("Following is a Topological Sort of the given graph")
---> 56 g.topologicalSort()

<ipython-input-8-cb05f6defc6c> in topologicalSort(self)
     37         for i in range(self.V):
     38             if visited[i] == False:
---> 39                 self.topologicalSortUtil(i,visited,stack)
     40 
     41         # Print contents of stack

<ipython-input-8-cb05f6defc6c> in topologicalSortUtil(self, v, visited, stack)
     21         for i in self.graph[v]:
     22             if visited[i] == False:
---> 23                 self.topologicalSortUtil(i,visited,stack)
     24 
     25         # Push current vertex to stack which stores result

<ipython-input-8-cb05f6defc6c> in topologicalSortUtil(self, v, visited, stack)
     21         for i in self.graph[v]:
     22             if visited[i] == False:
---> 23                 self.topologicalSortUtil(i,visited,stack)
     24 
     25         # Push current vertex to stack which stores result

<ipython-input-8-cb05f6defc6c> in topologicalSortUtil(self, v, visited, stack)
     21         for i in self.graph[v]:
     22             if visited[i] == False:
---> 23                 self.topologicalSortUtil(i,visited,stack)
     24 
     25         # Push current vertex to stack which stores result

<ipython-input-8-cb05f6defc6c> in topologicalSortUtil(self, v, visited, stack)
     20         # Recur for all the vertices adjacent to this vertex
     21         for i in self.graph[v]:
---> 22             if visited[i] == False:
     23                 self.topologicalSortUtil(i,visited,stack)
     24 

IndexError: list index out of range
  

Это IndexError: list index out of range вызвано тем, что в этом примере кода предполагается, что вершины нумеруются, начиная с нуля.

Список visited инициализируется как:

 visited = [False]*self.V 
  

Следовательно, если граф инициализирован с 5 вершинами, то индексы visited будут 0, 1, 2, 3, 4.

Затем позже функция topologicalSortUtil(self, v, visited, stack) выполняет строку 22 ниже, и вершина 5 выходит за пределы диапазона, поскольку диапазон варьируется от 0 до 4:

      21    for i in self.graph[v]:
---> 22        if visited[i] == False:
     23            self.topologicalSortUtil(i,visited,stack)
  

Следующий код, использующий индексацию вершин на основе нуля, работает так, как ожидалось.

 g = Graph(5) 

g.addEdge(0, 1)
g.addEdge(1, 2) 
g.addEdge(2, 3) 
g.addEdge(3, 4)

print("Following is a Topological Sort of the given graph")
g.topologicalSort() 
  

Вывод:

 Following is a Topological Sort of the given graph
[0, 1, 2, 3, 4]
  

Реализация топологической сортировки, которая работает с произвольными номерами вершин

Следующая реализация не требует от вас указания количества вершин, поскольку количество автоматически увеличивается всякий раз, когда новая вершина добавляется в граф с помощью add_edge метода.

Кроме того, вершины не обязательно должны начинаться с какого-либо определенного числа. Я пошел дальше и очистил форматирование, чтобы использовать стандартные соглашения об именах в змеином регистре.

 from collections import defaultdict 
  
class Graph: 
    def __init__(self): 
        self.graph = defaultdict(list) #dictionary containing adjacency List 
  
    def add_edge(self,u,v): 
        self.graph[u].append(v) 
  
    def topological_sort(self) -> list: 
        visited = set()
        reverse_topo = list() 
  
        vertices = set(self.graph.keys())
        for vertex in vertices: 
            if vertex not in visited:
                self._topological_sort_util(vertex, visited, reverse_topo) 
        return list(reversed(reverse_topo))
    
    def _topological_sort_util(self, vertex, visited, reverse_topo): 
        visited.add(vertex)

        for adj_vertex in self.graph[vertex]: 
            if adj_vertex not in visited: 
                self._topological_sort_util(adj_vertex, visited, reverse_topo) 
        reverse_topo.append(vertex)


g = Graph() 
g.add_edge(1, 2)
g.add_edge(2, 3) 
g.add_edge(3, 4) 
g.add_edge(4, 5) 
  
print("Following is a Topological Sort of the given graph")
vertices_topo_sorted = g.topological_sort() 
print(vertices_topo_sorted)
  

Вывод

 Following is a Topological Sort of the given graph
[1, 2, 3, 4, 5]