拓撲排序（卡恩算法）麻煩

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]