CODEWITHSUNDEEP
pythonpython-3.xalgorithmdepth-first-search
Sssssuppp
Sssssuppp

Reputation: 711

What is wrong with the DFS traversal?

I have tried out this DFS code for the following graph

      2___3___4___5
1 ___/
     \10___11___12__13

And this is the code:

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_traversal(self,node,visited):

        visited[node] = True
        print(node)
        for neighbour in self.graph[node]:
            if visited[neighbour] == False:
                self.DFS_traversal(neighbour,visited)

    def DFS(self,start_node):
        visited = [False]*len(self.graph)
        print(self.graph)
        self.DFS_traversal(start_node,visited)


g1 = Graph()
g1.addEdge(1,2)
g1.addEdge(2,3)
g1.addEdge(3,4)
g1.addEdge(4,5)
g1.addEdge(1,10)
g1.addEdge(10,11)
g1.addEdge(11,12)
g1.addEdge(12,13)
g1.DFS(1)

Finally when I executed this code I got an error. It prints from 1 to 5, but then, it gives an error saying IndexError: list index out of range. What is wrong with the code and why is this happening? Can someone please explain

Note: I searched on SO, but, I didn't seem to find a solution to this problem.

Upvotes: 0

Views: 102

Answers (1)

TrebledJ
TrebledJ

Reputation: 8987

visited is a list. But it's length only extends up to the number of nodes. Actually... not even that, as edges are directed in the current implementation. Since len(self.graph) is 7 (with keys 1, 2, 3, 4, 10, 11, 12), accessing visited[10] raises the index error, as it should. 6 is the largest index one can access.

Instead of

visited = [False]*len(self.graph)

use a dictionary, as your nodes aren't sequential.

visited = {node: False for node in self.graph}

I would also add a line to the addEdge method to model the edges as undirected:

    self.graph[v].append(u)

Upvotes: 1

Related Questions