python - 如何迭代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)

代码在范围上迭代，而不是在实际的节点键上迭代。

我尝试将其转换为:

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]