W4L3_Breadth First Search BFS

[@sayanghosh6996]

​def neighbors(graph: Graph, vertex: int) -> list:
row = graph.n
neighbors = []
​for i in range(row):
​if graph.hasedge(vertex, i):
neighbors.append(i)
return neighbors
​def bfs(graph: Graph, vertex: int) -> list:
output = []
q = Queue()
q.add(vertex)
output.append(vertex)
​while not q.isempty():
j = q.pop()
​for k in neighbors(graph, j):
​if k not in output:
q.add(k)
output.append(k)
return output

[@VivekKumarSinha25]

Here are the code snippets to generate Adjacency lists and Adjacency matrices for a graph. In the lecture, when using Adjacency matrix for BFS, we're obtaining the neighbors using a different function. But in case of BFS using Adj list, the provided code snippet in video does not take into account that we're working on a undirected graph and hence, the neighbors list, which is AList[i] gets messed up.
def AList(vertices: int, edges: List, directed = False):
AL = {}
for i in range(vertices):
AL[i] = []
for (i, j) in edges:
AL[i].append(j)
if not (directed and i in AL[j]):
AL[j].append(i)
return AL
def AMatrix(vertices: int, edges: List, directed = False):
Amat = np.zeros(shape=(vertices, vertices))
for (i, j) in edges:
Amat[i, j] = 1
if not directed:
Amat[j, i] = 1
return Amat

[@chanakya5035]

All the codes used and needed in this lecture.
'''Computing with Adjaceny Matrix'''
def neighbours(AMat, i):
nbrs = []
(rows, cols) = AMat.shape
for j in range(cols):
if AMat[i,j] == 1:
nbrs.append(j)
return(nbrs)
#print(neighbours(A,7))
class Queue:
def __init__(self):
self.queue = []
def addq(self,v):
self.queue.append(v)

def delq(self):
v = None
if not self.isempty():
v=self.queue[0]
self.queue = self.queue[1:]
return(v)

def isempty(self):
return(self.queue == [])

def __str__(self):
return(str(self.queue))
q = Queue()
#Adding elements in a queue
for i in range(3):
q.addq(i)
print(q)
print(q.isempty())
'''Deleting elemensts from a queue'''
for j in range(3):
print(q.delq(), q)
print(q.isempty())
"""BFS - Sir Madhavan Mukund"""
def BFS(AMat, v):
(rows,cols)=AMat.shape
visited = {}
for i in range(rows):
visited[i] = False
q = Queue() #Set up an empty queue.
visited[v] = True #Mark the initial vertex to be visited
q.addq(v) # Add it in into the queue
while (not q.isempty()):
j = q.delq()
for k in neighbours(AMat, j):
if not visited[k]:
visited[k] = True
q.addq(v)
return (visited)
'''Enhancing BFS to record paths'''
def BFSListPath(AList, v):
(visited, parent) = ({}, {})
for i in AList.keys():
visited[k]=False
parent[k] = -1
q = Queue()
q.addq(v)
while (not q.isempty()):
j = q.delq() # Take out the head of the queue.
for k in AList[j]: # We're using an Adjacency list, so I can pickup the list of neighbours of j,
if (not visited[k]):# And for every such k, which is a neighbor of j, if it has not been visited,
visited[k] = True# I set its visited status to True,
parent[k] = j # I set it's (k's) parent to j, because j is the reason k got added into this list.
q.addq(k) # and I add it to the queue
return(visited, parent)
"""Enhancing BFS to record distance"""
def BFSListPathLevel(AList,v):
(level, parent) = ({},{})
for i in AList.keys():
level[i] = -1
parent[i] = -1
q = Queue()
level[v] = 0
q.addq(v)
while (not q.isempty()):
j = q.delq() # Pick out first element of the queue.
for k in AList[j]: # I look at all it's (j's) neighbours,
if (level[k] == -1 ): # Instead of checking whether the vertex has been visited, I'll check whether the level has been assigned.
level[k] = level[j] + 1 # If the level has not been assigned / -1, it means that it's not been visited.
parent[k] = j #
q.addq(k) #
return (level, parent)

[@HereToShowYouMirror]

Ty 👍