Graph DFS algorithm using python shows list index out of range while accessing a utility list

Question

In the given program I have used a stack to implement DFS, with a utility list as stack. This is an iterative approach. The error is here as follows:

---> 19 if visited[i] == False:

IndexError: list index out of range

    from collections import defaultdict

    class Graph:
        def __init__(self):
            self.graph = defaultdict(list)

        def addEdge(self, u, v):
            self.graph[u].append(v)

        def dfs_stack(self, start, visited):
            stack = []
            stack.append(start)

            while(len(stack) != 0):
               #pop
               i = stack.pop()

               #if not visited: visit and print
               if visited[i] == False: THE ERROR IS ON THIS LINE
                 visited[i]=True
                 print(i , end = " ")

               #push all unvisited adjacent vertices
               for adj in self.graph[i]:
                  if visited[i] == False:
                    stack.append(i)


       def DFS(self, start):
          visited = [False]*(len(self.graph)+1)
          self.dfs_stack(start,visited)



g = Graph()
g.addEdge(1, 2) 
g.addEdge(2, 3) 
g.addEdge(3, 4) 
g.addEdge(4, 5) 
g.addEdge(5, 1) 
g.addEdge(2, 6)
g.addEdge(3, 6)
g.addEdge(8, 7)
g.DFS(8)

Always share the entire error message. Be careful, using == False is both unidiomatic and illogical. Also, variable and function names should follow the lower_case_with_underscores style. — AMC
– AMC, Commented Feb 8, 2020 at 18:52

SomeDude · Accepted Answer · 2020-02-08 21:39:32Z

2

The length of your graph is actually only 6 as your graph is :

{1: [2], 2: [3, 6], 3: [4, 6], 4: [5], 5: [1], 8: [7]}

you created visited[] to be of length 6 and when you access visited[8] it will throw IndexError: list index out of range.

You need to create visited[] be of length equal to lastvertex i.e. 8

edited Feb 8, 2020 at 21:39

answered Feb 8, 2020 at 15:10

SomeDude

14.3k5 gold badges26 silver badges49 bronze badges

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

Collectives™ on Stack Overflow

Graph DFS algorithm using python shows list index out of range while accessing a utility list

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related