Цикл обнаружения программы DFS завершается с ошибкой ключа

Question

Я пытаюсь реализовать обнаружение цикла в группе обеспечения доступности баз данных, и я использую словарь для отслеживания вершин, которые находятся в стеке рекурсии, устанавливая для их значений значение True в словаре. Как только они выходят, я устанавливаю их значение на единицу. Если я сталкиваюсь с одним и тем же узлом, пока он находится в стеке рекурсии, это цикл. Часть кода, которую я сравниваю со словарем стека рекурсии, пропускается. Я попытался отладить код, но я не понимаю, почему он не входит в часть сравнения в рекурсивной функции.

PS: Ребята, это не задание. Я просто тренируюсь.

График:

directed_cyclic_graph = {
'g': ['h'],
'a': ['h', 'b'],
'b': ['c'],
'd': ['b', 'e'],
'c': ['f'],
'e': ['f'],
'i': ['i'],
'f': ['d'],
'h': [None]
}

Код:

def cycle_detection_recursive(adjList, vertex, parent, recursion_stack):
for nv in adjList[vertex]:
    # In the case there is a cycle to itself
    if recursion_stack[nv] and nv is not None:
        print("Loop detected", nv, "-->", nv)
    if nv not in parent:
        if nv is not None:
            parent[nv] = vertex
            if not recursion_stack[nv]:

                print(nv, "enters recursion stack")
                recursion_stack[nv] = True
            else:
                print("Cycle detected:", "back edge", nv, "-->", vertex)
            cycle_detection_recursive(adjList, nv, parent, recursion_stack)
            recursion_stack[nv] = False
            print(nv, "exits recursion stack")

def cycle_detection(DAG):
recursion_stack = {}
parent = {}
adjList = DAG

for vertex in adjList:
    if vertex not in parent:

        print(vertex, "enters recursion stack")
        recursion_stack[vertex] = True
        parent[vertex] = None
        cycle_detection_recursive(adjList, vertex, parent, recursion_stack)
        recursion_stack[vertex] = False
        print(vertex, "exits recursion stack")

def main():

    print("Breakpoint")
    cycle_detection(directed_cyclic_graph)

Наконец, ошибка:

Traceback (most recent call last):
File "D:/Coding_Practice/Dynamic_Programming/graph_traversal.py", line 194, in <module>
b enters recursion stack
main()
File "D:/Coding_Practice/Dynamic_Programming/graph_traversal.py", line 190, in main
cycle_detection(directed_cyclic_graph)
File "D:/Coding_Practice/Dynamic_Programming/graph_traversal.py", line 177, in cycle_detection
cycle_detection_recursive(adjList, vertex, parent, recursion_stack)
File "D:/Coding_Practice/Dynamic_Programming/graph_traversal.py", line 146, in cycle_detection_recursive
if recursion_stack[nv] and nv is not None:
KeyError: 'c'