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.
functionbfs(n,m,edges,s){// Write your code here// we use this map to iterate edges in both directionsconstedgesMap=newMap();// map to keep track of the minimum distance between nodesconstdistanceMap=newMap();// Array of distances, should include whatever is in the distanche Map// plus the nodes that are unreachableconstdistanceArray=[];// fills mapsedges.forEach(([firstNode,secondNode])=>{// fills positive directionif(edgesMap.has(firstNode)){consttargetNodes=edgesMap.get(firstNode);targetNodes.add(secondNode);}else{// target nodesconsttargetNodes=newSet();targetNodes.add(secondNode);edgesMap.set(firstNode,targetNodes);}// fills negative directionif(edgesMap.has(secondNode)){consttargetNodes=edgesMap.get(secondNode);targetNodes.add(firstNode);}else{// target nodesconsttargetNodes=newSet();targetNodes.add(firstNode);edgesMap.set(secondNode,targetNodes)}});getMinimumDistances(edgesMap,distanceMap,s,n);for(leti=1;i<=n;i++){if(i!==s){distanceArray.push(distanceMap.get(i)||-1);}}returndistanceArray;}functiongetMinimumDistances(edgesMap,distances,start,numberOfNodes){consttargetNodes=edgesMap.get(start)||newSet();constnodesQueue=Array.from(targetNodes);// cleans the entry to avoid an infinity loopedgesMap.set(start,newSet());letnextLevelQueue=[];letlevel=1;letnodeDistancesToSet=numberOfNodes;while(nodesQueue.length>0&&nodeDistancesToSet>0){constnextNode=nodesQueue.shift();constnextTargetNodes=edgesMap.get(nextNode)||newSet();constnextNodesArray=Array.from(nextTargetNodes);nextLevelQueue.push(...nextNodesArray);edgesMap.set(nextNode,[]);if(!distances.get(nextNode)){// Once all distances have been set// we no longer need to keep looking// as deeper levels will only mean more distance between nodes// This fixes test case 5nodeDistancesToSet--;}constcurrentMinDistance=distances.get(nextNode)||Infinity;distances.set(nextNode,Math.min(currentMinDistance,level*6));if(nodesQueue.length===0){nodesQueue.push(...nextLevelQueue);nextLevelQueue=[];level++;}}returnlevel;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Breadth First Search: Shortest Reach
You are viewing a single comment's thread. Return to all comments →
Javascript