Python中的深度优先搜索错误：Key Error 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

这可能是因为缺少索引值或者列的序号。你可以在你的数据框中添加一个索引列，然后使用pandas的iloc语法来逐行遍历。比如：df.iloc['索引号码'].列名

Answer 2

你没有定义从顶点编号7出发的边。

Answer 3

你的图的实现中，没有那些出度为0的节点作为键。

所以，在这一行：

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

当你把7（或者4）作为item时，你试图访问graph[7]，但实际上并没有这个键。

你可以通过两种方式来解决这个问题：要么修改图的实现，让所有的键都有一个key:[]（包括那些没有出边的键），要么在访问之前先检查一下item是否在graph里。