The input graph to the bfs function is in the form of edge list representation.
from queue import deque def neighbour(s,visit,que): for i in l: if(i==s and i not in visit): que.append(i) visit.append(i) return que def bfs(start=0): que=deque() visit=[start] que.append(start) while(que): start=que.popleft() que=neighbour(start,visit,que) return visit l=[(0,1),(0,2),(1,2),(2,0),(2,3),(3,3)] visit=bfs(start=1)
This is quite inefficient (when it comes to large no. of edges) since in the neighbour function, it iterates through the entire edge-list every time even when many of the vertices in the edges are already visited in the previous function call.
So, a more efficient way would be to pop out the edges once they entered the if-condition so that in the function-call, there are lesser no. of edges to iterate through.
if (i==s and i not in visit): que.append(i) visit.append(i) l.remove(i)
But the iterator tends to just skip over to the next item in the list after removing a particular edge. Is there a way to implement an user-defined iterator function to improve the performance since reverse-iterators (i.e., _next__() exists but not _reverse__() ) don't exist?