Getting 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

似乎对于图中存在的每一个value, dfs_topsort算法都需要一个key。

所以我们需要为每个值包含键。第一个缺失的是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: [] }会得到您可能期望的输出。

Answer 2

我有和你一样的问题，我发现它没有从我的数据集中搜索3的值。我所做的是为我的3个值添加一个列表。您可能想添加如下内容:

graph_tasks = {...,
...,
3: [n,n],
...,
...,
}