Топологическая сортировка (алгоритм Кана)

Question

У меня возникли проблемы, обертывая мою голову вокруг моего кода во вложенном цикле. Я следую алгоритму Кана здесь на wiki: 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]