Topological sort (Kahn 's algorithm) trouble

Question

중첩 for 루프에서 내 머리를 감싸는 데 문제가 있습니다. 위키에 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]