Getting KeyError : 3
<p>Getting KeyError: 3 when trying to do the following to find the topological sort:</p>

<pre><code>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)
</code></pre>

<p>I'm getting KeyError: 3 for the above example. Why is that so? How can it be fixed?</p>

<p>It seems that the <code>dfs_topsort</code> algorithm needs a <code>key</code> for every <code>value</code> that exists in the graph. </p>

<p>So we need to include keys for each of the values. The first one that's missing is <code>3</code>, which caused the <code>KeyError: 3</code>, and also <code>13</code>. If we include these keys and give them empty values (because they are not connected to any other nodes) then it fixes the error.</p>

<p>Also, the other example you gave in the comment works because every value (right-hand side) ( <code>[2,3], [4, 5, 6], [4, 6], [5, 6], [6], []</code> ) is also in the Key values (left-hand side) [<code>1, 2, 3, 4, 5, 6</code>].</p>

<p>So using <code>graph_tasks = { 1: [2, 11], 2: [3], 3: [], 11: [12], 12: [13], 13: [] }</code> gives the output you may be expecting.</p>

<p>I hope this helps you.</p>

python graph dfs topological-sort