拓扑排序（卡恩算法）麻烦

Question

我在围绕我的代码嵌套for循环包装我的头困难。我在wiki上按照Kahn的算法：Kahn's。我不明白如果outgoingEdge具有每个endArray元素（m）的传入边缘，如何测试。

这是我到目前为止有：

def topOrdering(self, graph): 

    retList = [] 
    candidates = set() 
    left = [] 
    right = [] 

    for key in graph: 
     left.append(key) 
     right.append(graph[key]) 

    flattenedRight = [val for sublist in right for val in sublist] 

    for element in left: 
     if element not in flattenedRight: 
      #set of all nodes with no incoming edges 
      candidates.add(element) 

    candidates = sorted(candidates) 

    while len(candidates) != 0: 
     a = candidates.pop(0) 
     retList.append(a) 
     endArray = graph[a] 

     for outGoingEdge in endArray: 

      if outGoingEdge not in flattenedRight: 
       candidates.append(outGoingEdge) 
       #flattenedRight.remove(outGoingEdge) 

      del outGoingEdge 


    if not graph: 
     return "the input graph is not a DAG" 
    else: 
     return retList 

这里是我的可视化算法的图片。图形是一个邻接表的形式。

Answer 1

您可以分别存储indegree（输入边的数量），并在每次从空集移除顶点时减少计数。当count变为0时，将顶点添加到空集以待稍后处理。这里的例子：

def top_sort(adj_list): 
    # Find number of incoming edges for each vertex 
    in_degree = {} 
    for x, neighbors in adj_list.items(): 
     in_degree.setdefault(x, 0) 
     for n in neighbors: 
      in_degree[n] = in_degree.get(n, 0) + 1 

    # Iterate over edges to find vertices with no incoming edges 
    empty = {v for v, count in in_degree.items() if count == 0} 

    result = [] 
    while empty: 
     # Take random vertex from empty set 
     v = empty.pop() 
     result.append(v) 

     # Remove edges originating from it, if vertex not present 
     # in adjacency list use empty list as neighbors 
     for neighbor in adj_list.get(v, []): 
      in_degree[neighbor] -= 1 

      # If neighbor has no more incoming edges add it to empty set 
      if in_degree[neighbor] == 0: 
       empty.add(neighbor) 

    if len(result) != len(in_degree): 
     return None # Not DAG 
    else: 
     return result 

ADJ_LIST = { 
    1: [2], 
    2: [3], 
    4: [2], 
    5: [3] 
} 

print(top_sort(ADJ_LIST)) 

输出：

[1, 4, 5, 2, 3]