Получение KeyError: 3

Question

Как исключение KeyError: 3 при попытке выполнить следующие действия, чтобы найти топологическую сортировку:

def dfs_topsort(graph):   # recursive dfs with 
    L = []      # additional list for order of nodes 
    color = { u : "white" for u in graph } 
    found_cycle = [False] 
    for u in graph: 
     if color[u] == "white": 
      dfs_visited(graph, u, color, L, found_cycle) 
     if found_cycle[0]: 
      break 

    if found_cycle[0]:   # if there is a cycle, 
     L = []     # then return an empty list 

    L.reverse()     # reverse the list 
    return L      # L contains the topological sort 


def dfs_visited(graph, u, color, L, found_cycle): 
    if found_cycle[0]: 
     return 
    color[u] = "gray" 
    for v in graph[u]: 
     if color[v] == "gray": 
      found_cycle[0] = True 
      return 
     if color[v] == "white": 
      dfs_visited(graph, v, color, L, found_cycle) 
    color[u] = "black"  # when we're done with u, 
    L.append(u) 

graph_tasks = {1: [2,11], 
    2: [3], 
    11: [12], 
    12: [13] 
    } 
order = dfs_topsort(graph_tasks) 

for task in order: 
    print(task) 

Я получаю KeyError: 3 для приведенного выше примера. Почему это так? Как это можно исправить?

Answer 1

Кажется, что для алгоритма dfs_topsort требуется key для каждого value, который существует на графике.

Поэтому нам нужно включить ключи для каждого из значений. Первый, который отсутствует, - 3, что вызвало KeyError: 3, а также 13. Если мы включим эти ключи и дадим им пустые значения (потому что они не подключены к каким-либо другим узлам), то он исправляет ошибку.

Кроме того, другой пример, который вы дали в комментарии, работает, потому что каждое значение (правая сторона) ([2,3], [4, 5, 6], [4, 6], [5, 6], [6], []) также находится в значениях ключа (левая сторона) [1, 2, 3, 4, 5, 6].

Таким образом, используя graph_tasks = { 1: [2, 11], 2: [3], 3: [], 11: [12], 12: [13], 13: [] }, вы получите результат, который вы ожидаете.

Надеюсь, это вам поможет.