Depth First Search in python Error : Key Error 7

Question

enter image description here

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

Can you somehow provide a more comprehensive error report.

sshashank124
– sshashank124

2014-04-04 14:41:00 +00:00
Commented Apr 4, 2014 at 14:41 — sshashank124
– sshashank124, Commented Apr 4, 2014 at 14:41

amit · Accepted Answer · 2014-04-04 14:45:57Z

5

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.

answered Apr 4, 2014 at 14:45

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user189 · Accepted Answer · 2014-04-04 14:46:03Z

1

You did not define the edges going from the vertex number 7.

answered Apr 4, 2014 at 14:46

user189

6043 silver badges11 bronze badges

2 Comments

codegeek Over a year ago

This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post - you can always comment on your own posts, and once you have sufficient reputation you will be able to comment on any post.

Andrew Barber Over a year ago

@codegeek Actually, I think this is an attempt to answer the question. It's short and simple - and perhaps it's wrong - but it does try to answer.

Achyut Srivastava · Accepted Answer · 2020-07-01 18:53:42Z

0

It can be due to absent index value or column serial number. What you can do is you can add index column in your data frame and then use pandas iloc syntax to loop through each row. Ex: df.iloc['index number'].columnname

answered Jul 1, 2020 at 18:53

Achyut Srivastava

1

Collectives™ on Stack Overflow

Depth First Search in python Error : Key Error 7

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related