如何遍历defaultdict？

Question

我有下面的代码来建立拓扑顺序：

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

我怎么才能解决这个问题？

Answer 1

在您的类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]

Answer 2

dict.items()返回(key, value)的元组。

尝试更改您的代码，以获得密钥。

for i in self.graph.keys():

或者这个

for i, _ in self.graph.items():