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.
Breadth First Search: Shortest Reach
Breadth First Search: Shortest Reach
+ 0 comments python3 solution using for loop to bfsdef bfs(n, m, edges, s): # Result dic r = {i:-1 for i in range(1,n+1) if i != s} r[s] = 0 # make graph g = {i:[] for i in range(1,n+1)} for j,k in edges: g[j].append(k) g[k].append(j) # bfs with lable check = [s] marked = set() for i in check: if i not in marked: marked.add(i) for j in g[i]: if j not in check: r[j] = r[i] + 6 check.append(j) del r[s] return list(r.values())
+ 0 comments def bfs(n, m, edges, s): graph = [[0] * n for i in range(n)] for edge in edges: graph[edge[0] - 1][edge[1] - 1] = 6 # make 0 based index graph[edge[1] - 1][edge[0] - 1] = 6 # make 0 based index dist = [-1] * n visited = [False] * n dist[s - 1] = 0 q = Queue() q.put(s - 1) while not q.empty(): cur = q.get() visited[cur] = True for i in range(n): if graph[cur][i] > 0 and not visited[i]: dist[i] = dist[cur] + graph[cur][i] q.put(i) visited[i] = True del dist[s - 1] return dist
+ 0 comments js
const getDistances = (nodes, edges, s) => { const visited = new Map(); const distanceMap = new Map(); const edgesMap = new Map(); nodes.forEach((nodeNumber) => { visited.set(nodeNumber, 0); distanceMap.set(nodeNumber, 0); edgesMap.set(nodeNumber, []); }); edges.forEach(([u, w]) => { edgesMap.get(u).push(w); edgesMap.get(w).push(u); }); let queue = []; queue.push(s); while (queue.length > 0) { const u = queue.shift(); const uEdges = edgesMap.get(u); visited.set(u, 1); for(let j = 0; j < uEdges.length; j++) { const w = uEdges[j]; if (visited.get(w) === 0) { visited.set(w, 1); queue.push(w); distanceMap.set(w, distanceMap.get(u) + 6); } } visited.set(u, 2); } let distances = Array.from(distanceMap.entries()); distances = distances.filter(([node]) => { return node !== s; }); distances = distances.map(([node, dist]) => { return dist === 0 ? -1 : dist; }); return distances; } function bfs(n, m, edges, s) { // Write your code here const nodes = []; for (let i = 1; i <= n; i ++) { nodes.push(i); } return getDistances(nodes, edges, s); }
+ 0 comments My Javascript Code
function bfs(n, m, edges, s) { // Write your code here const graph={} for(let [src,dest] of edges){ if (!graph[src]) { graph[src] = []; } if(!graph[dest]) { graph[dest] = []; } graph[src].push(dest) graph[dest].push(src) } console.log(graph) let dist=Array(n+1).fill(-1,1) let visited=new Set() let queue=[]; queue.push(s); dist[s]=0 visited.add(s) while(queue.length>0){ let u=queue.shift(); if(graph[u]) { for (let child of graph[u]) { if (!visited.has(child)) { visited.add(child); dist[child] = dist[u]+6; queue.push(child); } } } console.log(queue) } dist.splice(s,1) console.log(dist) return Object.values(dist) }
+ 0 comments public static List<Integer> bfs(int n, int m, List<List<Integer>> edges, int s) { Map<Integer,Integer> edgeMap = new HashMap<>(); List<Integer> res = new ArrayList<>(); int[] distance = new int[n]; for(int i = 0 ; i<n && i!=s-1;i++){ distance[i] = Integer.MAX_VALUE; } boolean[] visited = new boolean[n]; visited[s-1]=true; int[][] edgesMatrix = new int[n][n]; for(int i = 0;i<edges.size();i++){ edgesMatrix[edges.get(i).get(0)-1][edges.get(i).get(1)-1]=1; edgesMatrix[edges.get(i).get(1)-1][edges.get(i).get(0)-1]=1; } Queue<Integer> q = new ArrayDeque<Integer>(); q.add(s-1); while(!(q.isEmpty())){ int current= q.poll(); for(int i = 0 ;i<edgesMatrix.length;i++){ if(edgesMatrix[current][i]==1&& !visited[i]){ visited[i] = true; q.add(i); distance[i]=distance[current]+6; } } } System.out.println(Arrays.toString(distance)); for(int i = 0 ;i<distance.length;i++){ if(i!=s-1&&distance[i]!=0){ res.add(distance[i]= distance[i]==Integer.MAX_VALUE ?-1 : distance[i]); } if(i!=s-1&&distance[i]==0){ distance[i]=-1; res.add(distance[i]); } } return res; }
Load more conversations
Sort 654 Discussions, By:
Please Login in order to post a comment