Interview Questions

Breadth First Search - Java

Problem Statement

Given an undirected graph consisting of nodes (labelled 1 to N) where a specific given node represents the start position and an edge between any two nodes is of length units in the graph.

It is required to calculate the shortest distance from start position (Node S) to all of the other nodes in the graph.

Note 1: If a node is unreachable , the distance is assumed as .
Note 2: The length of each edge in the graph is units.

Input Format

The first line contains , denoting the number of test cases.
First line of each test case has two integers , denoting the number of nodes in the graph and , denoting the number of edges in the graph.
The next lines each consist of two space separated integers , where and denote the two nodes between which the edge exists.
The last line of a testcase has an integer , denoting the starting position.

Constraints



Output Format

For each of test cases, print a single line consisting of space-separated integers, denoting the shortest distances of the N-1 nodes from starting position . This will be done for all nodes same as in the order of input 1 to N.

For unreachable nodes, print .

Sample Input

2
4 2
1 2
1 3
1
3 1
2 3
2

Sample Output

6 6 -1
-1 6

import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.concurrent.ArrayBlockingQueue;

public class Solution {

    public static void main(String[] args)
        {
                Scanner sc = new Scanner(System.in);
                int t = sc.nextInt();
               
                for(int i=0;i<t;i++)
                {
                        int n = sc.nextInt();
                        Map<String,Node> nodes = createNodes(n);
                        int e = sc.nextInt();
                        Set<Node> reachable = new HashSet<Node>();
                        for(int k=0;k<e;k++)
                        {
                                String start = sc.next();
                                String end = sc.next();
                               
                                Node st = nodes.get(start);
                                Node en = nodes.get(end);
                                st.addToLinks(en);
                en.addToLinks(st);
                reachable.add(st);
                                reachable.add(en);
                        }
                        String startNde = sc.next();
                        Node startNode = nodes.get(startNde);
                        getShortestPath(startNode, nodes,reachable);
            System.out.println();
                }
               
                /*Node one = new Node("1");
                Node two = new Node("2");
                Node three = new Node("3");
                Node four = new Node("4");
                Node five = new Node("5");
               
                one.addToLinks(two);
                one.addToLinks(three);
                three.addToLinks(four);
                four.addToLinks(five);
               
                System.out.println(four.search(one));*/

        }
       
        public static Map<String,Node> createNodes(int n)
        {
                Map<String,Node> nodeMap = new LinkedHashMap<String,Node>();
               
                for(int i=1;i<=n;i++)
                {
                        nodeMap.put(i+"", new Node(i+""));
                }
               
                return nodeMap;
        }
       
        public static void getShortestPath(Node s,Map<String,Node> nodes,Set<Node> existing)
        {
                for(Node n:nodes.values())
                {
                        if(n.equals(s))
                                continue;
                        else if(!existing.contains(n)){
                                System.out.print(-1+" ");
                        }
                        else
                        {
                                s.setLength(0);
                ArrayBlockingQueue<Node> q = s.getQueue();
                q.clear();
               
                q.add(s);
               int l=s.searchBFS(n);
                                if(l>0)
                                System.out.print(l*6+" ");
                                else
                                        System.out.print(-1+" ");
                        }
                        setTraversedForAll(existing);
                }
        }
   
    public static void setTraversedForAll(Set<Node> reachable)
        {
                for(Node n:reachable)
                {
                        n.setTraversed(false);
                }
        }

}

 class Node {

        private String name;
       
        private Set<Node> links = new HashSet<Node>();
     
     private boolean isTraversed = false;
       
        public Node(String name)
        {
                this.name = name;
        }
       
     public boolean isTraversed() {
                return isTraversed;
        }

 
        public void setTraversed(boolean isTraversed) {
                this.isTraversed = isTraversed;
        }
       
        public void addToLinks(Node link)
        {
                links.add(link);
        }


        @Override
        public int hashCode() {
                final int prime = 31;
                int result = 1;
                result = prime * result + ((name == null) ? 0 : name.hashCode());
                return result;
        }


        @Override
        public boolean equals(Object obj) {
                if (this == obj)
                        return true;
                if (obj == null)
                        return false;
                if (getClass() != obj.getClass())
                        return false;
                Node other = (Node) obj;
                if (name == null) {
                        if (other.name != null)
                                return false;
                } else if (!name.equals(other.name))
                        return false;
                return true;
        }
       
     private ArrayBlockingQueue<Node> queue = new ArrayBlockingQueue<>(10000);
    private int length = 0;
   
   
    public ArrayBlockingQueue<Node> getQueue() {
        return queue;
    }


    public void setQueue(ArrayBlockingQueue<Node> queue) {
        this.queue = queue;
    }


    public int getLength() {
        return length;
    }


    public void setLength(int length) {
        this.length = length;
    }


    public int searchBFS(Node f)
    {
        Node s = queue.poll();
        while(s!=null)
        {
           
        if(s.isTraversed==true)
        {
            s=queue.poll();
            continue;
        }
    //    System.out.println("name---"+s.name);
        if(s.links.contains(f))
        {
            if(s.length==0)
                return 1;
            return s.length+1;
        }
        else{
            //length++;
        }
        if(s.links.size()>0)
        {
            s.isTraversed= true;
            queue.addAll(s.links);
            addLength(s.links,s);
            //length++;
        }
        else
        {
            s.isTraversed= true;
            s = queue.poll();
            continue;
        }
       
       
        s = queue.poll();
        }
        return 0;
    }
   
    public void addLength(Set<Node> n,Node s)
    {
        for(Node e:n)
        {
            if(e.getLength()==0)
            e.setLength(s.length+1);
           
        }
    }
               
                public int search(Node f,Node start)
        {
                //System.out.println("print- "+f.name+"- this -"+this.name);
               
                if(links.contains(f))
                                {
                              return 1;
                                }
                int sl = 0;
                if(this.isTraversed==true)
                        return sl;
                for(Node n:this.links)
                {
                        this.isTraversed=true;
                        if(n.equals(start))
                                continue;  
                        int k = n.search(f,this);
                        if(k>0){
                                 int l = 1 + k;
                        if(sl==0)
                        {
                                sl = l;
                        }else if(l<sl)
                        {
                                sl = l;
                        }
                if(sl==2)
                        {
                                return sl;
                        }
                        }
                }
               
               
                return sl;
        }
       
}