深度优先在python中搜索错误:密钥错误7

Question

我编写了以下python程序来执行给定图形的DFS,但在执行后它给出了错误:键错误7.我的代码有什么问题？

output=[]
graph = {
            9:[8,7,6],
            8:[5,4],
            6:[3,2],
            5:[1,0]
        }

def dfs(graph,root):
    stack=[]
    visited=set()

    stack.append(root)
    output.append(str(root))
    visited.add(root)

    while not(stack==[]):
        for item in graph[root]:

            if item not in visited:
                stack.append(item)
                visited.add(item)
                output.append(str(item))

            if set(graph[item]).union(visited)==visited:
                stack.pop(-1)
                root=stack[len(stack)-1]
                continue

            root=item

dfs(graph,9)
print(" ".join(output))

---

在添加@amit给出的建议后,问题仍然没有解决,我已经编写了以下代码并且输出的输出不正确,请帮忙!

output=[]
graph = {
           1:[2,3],
           2:[4,5],
           3:[6,7],
           4:[],
           5:[],
           6:[],
           7:[]
        }

def dfs(graph,root):
    stack=[]
    visited=set()

    stack.append(root)
    output.append(str(root))
    visited.add(root)

    while not(stack==[]):
        for item in graph[root]:

            if item not in visited:
                stack.append(item)
                visited.add(item)
                output.append(str(item))

            if set(graph[item]).union(visited)==visited:
                stack.pop(-1)
                if not(stack==[]):
                    root=stack[len(stack)-1]
                else:
                    break
                continue

            root=item

dfs(graph,1)
print(" ".join(output))

Answer 1

您的图表实现没有带有d_out(v)=0键的节点.

所以,在这一行:

        if set(graph[item]).union(visited)==visited:

当你把7(或4)作为item,你试图访问graph[7]- 但没有这样的键.

您可以通过更改图形实现以key:[]使所有键(包括没有出口边缘的密钥),或者在尝试访问它之前添加检查条件以检查是否item存在来克服graph它.