Topological Sort with simple input results in "IndexError: list index out of range"

Question

我在研究拓扑排序时遇到了GeeksforGeek's Python code。

# 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

Answer 1

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]

Topological Sort with simple input results in "IndexError: list index out of range"

Topological Sort with simple input results in "IndexError: list index out of range"

python

list

topological-sort

堆栈跟踪

适用于任意顶点数的拓扑排序实现

输出