深度在python错误优先搜索：关键错误7 [英] Depth First Search in python Error : Key Error 7

问题描述

我已经写了下面的Python程序来执行 DFS 对于给定的图形，但执行后，给出了错误：键错误7 。什么是错误的，我code？

 输出= []
图= {
            9：[8,7,6]
            8：[5,4]，
            6：[3,2]，
            5：[1,0]
        }

高清DFS（图，根）：
    堆栈= []
    走访=集（）

    stack.append（根）
    output.append（STR（根））
    visited.add（根）

    而不是（堆栈== []）：
        在图[根]项目：

            如果不是在参观项目：
                stack.append（项目）
                visited.add（项目）
                output.append（STR（项目））

            。如果设置（图[项目]）联盟（参观）==参观：
                stack.pop（-1）
                根=栈[LEN（栈）-1]
                继续

            根=项目

DFS（图9）
打印（。加入（输出））
 

---

不过这个问题将通过@amit我写了下面的code，它是给不正确的输出，请帮忙给建议后，仍没有解决！

 输出= []
图= {
           1：[2,3]，
           2：[4,5]，
           3：[6,7]，
           4：[]，
           5：[]，
           6：[]，
           7：[]
        }

高清DFS（图，根）：
    堆栈= []
    走访=集（）

    stack.append（根）
    output.append（STR（根））
    visited.add（根）

    而不是（堆栈== []）：
        在图[根]项目：

            如果不是在参观项目：
                stack.append（项目）
                visited.add（项目）
                output.append（STR（项目））

            。如果设置（图[项目]）联盟（参观）==参观：
                stack.pop（-1）
                如果不是（堆栈== []）：
                    根=栈[LEN（栈）-1]
                其他：
                    打破
                继续

            根=项目

DFS（图中，1）
打印（。加入（输出））
 

解决方案

您图形执行不具有作为键与 D_OUT（V）=​​ 0 节点。

那么，在这一行：

 如果设置（图[项目]）联盟（参观）==访问：
 

当你把7（或4）项目，您试图访问图[7] - 但有没有这样的关键。

您可以通过克服它改变图实现有一个键：[] 所有密钥（包括那些没有出边），或者通过添加检查的条件，以检查是否项目是图试图访问它。

I have written following python program to perform a DFS for the given graph, but after execution it gives the error : Key Error 7. What is wrong in my code?

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))

---

Still the problem is not solved after adding suggestions given by @amit i have written the following code and it is giving incorrect output, please help!

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))

解决方案

Your graph implementation does not have nodes with d_out(v)=0 as keys.

So, in this line:

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

When you put 7 (or 4) as item, you try to access graph[7] - but there is no such key.

You can overcome it by either changing the graph implementation to have a key:[] for all keys (including those with no out-edges), or by adding a check to the condition to check if item is in graph before attempting to access it.

这篇关于深度在python错误优先搜索：关键错误7的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！