拓扑排序给出不正确的结果

Question

我是算法新手，正在尝试拓扑排序 (https://www.educative.io/collection/page/6151088528949248/4547996664463360/5657624383062016)，但卡在了这里。当我给出数值时它工作正常，但是当给出字符串依赖时它给出不正确的输出

我的路径如下：

'sA'-->'sB' ,

'sA'--> 'sC' ,

'sB'--> 'sD'

到目前为止尝试过：

from collections import defaultdict
    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)
            stack.insert(0,v)
        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 contents of stack
            print(stack)   
    g= Graph(4)
    g.addEdge('sA', 'sB')
    g.addEdge('sA', 'sC')
    g.addEdge('sB', 'sD')
    print(g.graph)    
    print("Following is a Topological Sort of the given graph")
    g.topologicalSort()

预期输出：

sA -> sB -> sD -> sC

目前我得到 [3,2,1,0]

Answer 1

在self.graph中编码的图的结构允许图的顶点是任意对象（数字、字符串等）。但是，在对图进行排序时，您会使用整数索引及其在 visited 列表中的相应值来跟踪访问了哪些顶点。由于整数和顶点标签之间没有映射，因此会产生错误的结果。如果 self.graph 是一个普通字典，这个问题就会很明显，因为行

for i in self.graph[v]

会产生错误（您作为键 v 传递的整数不是 self.graph 中的有效键）。但是，由于 self.graph 是默认字典，因此会产生默认值，即空列表。

您可以修复它，例如如下：

from collections import defaultdict
class Graph:
    def __init__(self):
        self.graph = defaultdict(list) #dictionary containing adjacency List
    # 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,non_visited,stack):        
        # Recur for all the vertices adjacent to this vertex    
        for i in self.graph[v]:
            if i in non_visited:
                non_visited.remove(i)
                self.topologicalSortUtil(i,non_visited,stack)
        stack.insert(0,v)

    def topologicalSort(self):
        # set of all vertices
        non_visited = set(self.graph.keys()).union(*list(self.graph.values()))
        stack =[]
        while non_visited:
            v = non_visited.pop()
            self.topologicalSortUtil(v,non_visited,stack)    
        # Print contents of stack
        print(stack)   

g= Graph()
g.addEdge('sA', 'sB')
g.addEdge('sA', 'sC')
g.addEdge('sB', 'sD')
print(g.graph)    
print("Following is a Topological Sort of the given graph")
g.topologicalSort()

此代码将 visited 列表替换为集合 non_visited，该集合在开头包含所有顶点。然后在访问顶点时将它们一一删除。

拓扑排序给出不正确的结果

Topological Sort giving incorrect result

python

algorithm

graph-algorithm