We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#!/bin/python3importmathimportosimportrandomimportreimportsys## Complete the 'bfs' function below.## The function is expected to return an INTEGER_ARRAY.# The function accepts following parameters:# 1. INTEGER n# 2. INTEGER m# 3. 2D_INTEGER_ARRAY edges# 4. INTEGER s#classNode:def__init__(self,val):self.val=valself.visited=Falseself.neighbors=[]def__repr__(self):returnstr(self.val)def__str__(self):returnstr({"node":self.val,"neighbors":self.neighbors,"visted":self.visited})defadd_neighbor(self,neighbor):ifneighbor.val!=self.valandneighbor.valnotinself.neighbors:self.neighbors.append(neighbor.val)defbfs(n,m,edges,s):# Write your code here#### step one construct the graph structuregraph={}# init the graph with nodes with no edgesforiinrange(n):node=i+1graph[node]=Node(node)# add edges to the graphforedgeinedges:n1,n2=edgen1,n2=graph[n1],graph[n2]n1.add_neighbor(n2)n2.add_neighbor(n1)# print(graph)#### step 2 calculate distances from the graph datastructurecost=6queue=[s]#startoffwiththestartnodedistances=[-1]*n#initalldistanceswith-1distances[s-1]=0#thestartnodehasadistanceofzerowhilequeue:node=queue.pop(0)node=graph[node]ifnode.visited:continue#moveontothenextiteminthequeuenode.visited=Trueforneighborinnode.neighbors:queue.append(neighbor)neighbor=graph[neighbor]# assumes that the graph nodes ids start with 1 and are sequential # updates distancescurrent_node_idx=node.val-1neighbor_node_idx=neighbor.val-1# only update distance if it hasn't been updated already# this is for the case when I have 1-2 and also 2-1ifdistances[neighbor_node_idx]==-1:distances[neighbor_node_idx]=distances[current_node_idx]+cost# print("current node idx",current_node_idx)# print("neighbor node idx",neighbor_node_idx)# print("distances list", distances)# print("current node",node)# print("neighbornode",neighbor)# print(queue)distances.pop(s-1)#poptheindexofthestartnode# print(distances)returndistancesif__name__=='__main__':fptr=open(os.environ['OUTPUT_PATH'],'w')q=int(input().strip())forq_itrinrange(q):first_multiple_input=input().rstrip().split()n=int(first_multiple_input[0])m=int(first_multiple_input[1])edges=[]for_inrange(m):edges.append(list(map(int,input().rstrip().split())))s=int(input().strip())result=bfs(n,m,edges,s)fptr.write(' '.join(map(str,result)))fptr.write('\n')fptr.close()
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
BFS: Shortest Reach
You are viewing a single comment's thread. Return to all comments →
python3 sol