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[0]==s and i[1] not in visit):
que.append(i[1])
visit.append(i[1])
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.
Like this:
if (i[0]==s and i[1] not in visit):
que.append(i[1])
visit.append(i[1])
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?