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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Breadth First Search: Shortest Reach
  5. Discussions

Breadth First Search: Shortest Reach

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 654 Discussions, By:

recency

Please Login in order to post a comment

  • xl2860
    2 days ago+ 0 comments
    python3 solution using for loop to bfs
    def 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|
    Permalink
  • akolodziejczak11
    2 weeks ago+ 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|
    Permalink
  • beto_kellyano
    4 weeks ago+ 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|
    Permalink
  • yashbaddi
    2 months ago+ 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|
    Permalink
  • EnesBaser
    2 months ago+ 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;
            
    
        }
    
    2|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy