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