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. BFS: Shortest Reach in a Graph
  2. Discussions

BFS: Shortest Reach in a Graph

Problem
Submissions
Leaderboard
Discussions
Editorial

    You are viewing a single comment's thread. Return to all comments →

  • piyush121
    7 years ago+ 18 comments

    Here is my Adjacency list based standard BFS solution (in Java 7) for your reference though I recommend reading only when you've spent a good amount of time on this problem.

    public static class Graph {
            List<List<Integer>> adjLst; 
            int size;
            public Graph(int size) {
                adjLst = new ArrayList<>();
                this.size = size;
                while(size-- > 0)//Initialize the adjancency list.
                    adjLst.add(new ArrayList<Integer>());
            }
    
            public void addEdge(int first, int second) {
                adjLst.get(first).add(second);
                adjLst.get(second).add(first); 
    // For undirected graph, you gotta add edges from both sides.
            }
            
            public int[] shortestReach(int startId) { // 0 indexed
                int[] distances = new int[size];
                Arrays.fill(distances, -1); // O(n) space.
                Queue<Integer> que = new LinkedList<>();
                
                que.add(startId); // Initialize queue.
                distances[startId] = 0;
                HashSet<Integer> seen = new HashSet<>(); //O(n) space. Could be further optimized. I leave it to you to optimize it.
                
                seen.add(startId);
                while(!que.isEmpty()) { // Standard BFS loop.
                    Integer curr = que.poll();
                    for(int node : adjLst.get(curr)) {
                        if(!seen.contains(node)) {
                            que.offer(node);
                // Right place to add the visited set.
                            seen.add(node); 
                // keep on increasing distance level by level.
                            distances[node] = distances[curr] + 6; 
                        }
                    }
                }   
                return distances;
            }
        }
    
    97|
    Permalink
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy