python - 简单输入的拓扑排序导致“IndexError:列表索引超出范围”
问题描述
我在学习拓扑排序,偶然发现了GeeksforGeek 的 Python 代码。
# 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]
推荐阅读
- java - RecyclerView 监听器的简单实现
- python - Django为他的汽车上传当前用户的图像
- python - 在numpy数组中计算值更改发生之前的长度和转换次数的最佳方法(最好是numpythonic)?
- spring-boot - 在 Tomcat 9 上部署 Spring Boot 应用程序时,Apache 服务器出现问题:状态 404 - 未找到
- html - vuejs中的利息计算器
- r - ggplot2中的分轴图
- python - 来自 JSON 的空 pandas 数据框
- ruby - 如何让 ActiveRecord 保存我的表格?
- github - GitHub 无法创建服务挂钩订阅 无法在所选 GitHub 上配置服务...资源无法通过集成访问
- r - 计算滞后,但使用 dplyr 按两个类别分组