0

I am trying to create a BFS in python. While I am proper adjacency list but Python is showing "list index out of range" error, also BFS answer is not correct all the time.

Below is the python code, I have added edges, (1, 2), (2, 3) and (3, 3)

I am trying to find BFS from vertex 2,

from collections import defaultdict

# This class represents a directed graph using adjacency
# list representation
class Graph:

    # Constructor
    def __init__(self):

        # default dictionary to store graph
        self.graph = defaultdict(list)

    # function to add an edge to graph
    def addEdge(self,u,v):
        self.graph[u].append(v)

    # Function to print a BFS of graph
    def BFS(self, s):

        # Mark all the vertices as not visited
        visited = [False]*(len(self.graph))

        # Create a queue for BFS
        queue = []

        # Mark the source node as visited and enqueue it
        queue.append(s)
        visited[s] = True

        while queue:

            # Dequeue a vertex from queue and print it
            s = queue.pop(0)
            print s,

            # Get all adjacent vertices of the dequeued
            # vertex s. If a adjacent has not been visited,
            # then mark it visited and enqueue it
            for i in self.graph[s]:

                if visited[i] == False:

                    queue.append(i)
                    visited[i] = True




# Create a graph 
g = Graph()

g.addEdge(1, 2)
g.addEdge(2, 3)
g.addEdge(3, 3)

print "Following is Breadth First Traversal (starting from vertex 2)"
g.BFS(2)

The error it is showing;

Following is Breadth First Traversal (starting from vertex 2)
2
Traceback (most recent call last):
  File "test.py", line 58, in <module>
    g.BFS(2)
  File "test.py", line 42, in BFS
    if visited[i] == False:
IndexError: list index out of range

Not sure, why it is showing out of range. I already initialised vertex[1], vertex[2] and vertex[3] as False. Also, graph[1], graph[2] and graph[3] is maintaining proper adjacency list.

Also, the BFS answer should be 2 3 but it is giving only 2

2 Answers 2

1

The visited array has length 3 therefore visited[3] is out of bounds.

The issue is mainly due to the fact that python lists are indexed from 0 and therefore the line visited = [False]*(len(self.graph)) won't create an entry visited[len(self.graph)].

Moreover to debug I would suggest you to print i and the visited list before the instruction that fails to see what is going on.

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

Comments

0

Replace visited = [False]*(len(self.graph))
With this visited = [False]*(len(self.graph)+1)

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.