python - 如何迭代defaultdict?
问题描述
我有以下代码构成拓扑顺序:
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
self.V = 0 #number of nodes
def addEdge(self,u,v):
self.graph[u].append(v)
self.V = self.V + 1
def topologicalSortUtil(self,v,visited,stack):
visited[v] = True
for i in self.graph[v]:
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
stack.insert(0,v)
# topologicalSortUtil()
def topologicalSort(self):
# Mark all the vertices as not visited
visited = [False]*self.V
stack =[]
for i in range(self.V):
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
print stack
g= Graph()
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
g.topologicalSort()
它给:
[5, 4, 3, 2, 1, 0]
现在,我希望我的代码能够将字符串作为键进行处理:
g.addEdge('f', 'c')
g.addEdge('f', 'a')
g.addEdge('e', 'a')
g.addEdge('e', 'b')
g.addEdge('c', 'd')
g.addEdge('d', 'b')
(只需将数字更改为字母... 0='a'、1='b' 等)但是这不起作用。
它应该给出:
['f', 'e', 'd', 'c', 'b', 'a']
问题在这里:
for i in range(self.V):
if visited[i] is False:
self.topologicalSortUtil(i, visited, stack)
代码会遍历range
而不是遍历实际的节点键。
我试图将其转换为:
for i in self.graph.items():
但它不起作用。
TypeError: list indices must be integers or slices, not tuple
我怎样才能解决这个问题?
解决方案
有一些东西可以在你的类中概括Graph
为接受字母和数字作为顶点的名称。
这是一个建议:
class Graph:
def __init__(self, name_of_vertices):
self.graph = collections.defaultdict(list)
self.name_of_vertices = name_of_vertices # define all vertices by name
def add_edge(self, v, other_v):
self.graph[v].append(other_v)
def _topological_sort(self, v, visited, stack):
visited[v] = True
for other_v in self.graph[v]:
if not visited[other_v]:
self._topological_sort(other_v, visited, stack)
stack.insert(0, v)
def topological_sort(self):
# Mark all the vertices as not visited
visited = {
v: False
for v in self.name_of_vertices}
stack = []
for v in self.name_of_vertices:
if not visited[v]:
self._topological_sort(v, visited, stack)
print(stack)
然后你可以使用这个:
g = Graph(['z', 'a', 'b', 'c', 'd', 'e'])
g.add_edge('e', 'b')
g.add_edge('e', 'z')
g.add_edge('d', 'z')
g.add_edge('d', 'a')
g.add_edge('b', 'c')
g.add_edge('c', 'a')
g.topological_sort()
# prints: ['e', 'd', 'b', 'c', 'a', 'z']
g = Graph(list(range(6)))
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)
g.topological_sort()
# prints: [5, 4, 2, 3, 1, 0]
推荐阅读
- reactjs - 如何通过 JSX 中的 map/if 或三元运算符动态地将数据添加到表中
- r - powerBI中的自定义R视觉超时
- ios - 带有渐变填充的 iOS Swift Highcharts Pie 是黑色的
- vb.net - 如何使用 Visual Basic VB.Net 访问 iCloud 非默认 Outlook 文件夹
- sql - 如何根据设备ID选择某些设备发送的最后一条消息?
- c# - 如何解决错误: FlurlHttpException: Call failed with status code 400 (Content-Length can't beyond 10485760 bytes (10MB)
- r - 预测值的 RMSE 和 MAE 优于基准,但预测值只有一半时间接近实际值
- python - 在熊猫数据框中过滤具有多个唯一值的列
- kotlin - 函数kotlin中前面没有对象的flatMap
- list - 使用 ForEach (SwiftUI) 的偶数行和奇数行