EndSemq1.java

import java.util.*;

public class EndSemq1 {

    public static int bfs(ArrayList<ArrayList<Integer>> list,int arr1[],int arr2[]){

        Queue<Integer> queue = new LinkedList<>();
        
        boolean[] visited = new boolean[list.size()];

        for(int i=0;i<arr1.length;i++){
            queue.add(arr1[i]);
            visited[i] = true;
        }
        
    
        int diff=(int)10e9;

        while (!queue.isEmpty()) {
            
            int currentNode = queue.poll();
            
            for (int neighbor : list.get(currentNode)){
                
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                    for(int i:arr2){
                        if(neighbor== i){
                            diff=Math.min(diff,Math.min(Math.abs(arr1[0]-neighbor),Math.abs(arr1[1]-neighbor)));
                        }
                    }
                }
            }
        }

        return diff;
    }
    

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);

        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        System.out.println("Enter the number of verices");
        int V=sc.nextInt();
        System.out.println("Enter the number of edges");
        int E=sc.nextInt();

        for(int i=0;i<V;i++){
            list.add(new ArrayList<Integer>());
        }

        System.out.println("Define the graph...");

        for(int i=0;i<E;i++){
            System.out.println("Enter the start point");
            int startpoint=sc.nextInt();
            System.out.println("Enter the end point");
            int endpoint=sc.nextInt();
            list.get(startpoint).add(endpoint);
            list.get(endpoint).add(startpoint);
        }

        System.out.println("The graph is:");

        for(int i=0;i<list.size();i++){
            System.out.print(i+" : ");
            for(int j:list.get(i)){
                System.out.print(j+" -> ");
            }
            System.out.println();
        }

        System.out.println("Define the subsets...");

        System.out.println("Subset 1, enter the size");

        int size1=sc.nextInt();

        int arr1[]=new int[size1];

        for(int i=0;i<size1;i++){
            System.out.println("Enter the node");
            int node=sc.nextInt();
            arr1[i]=node;
        }

        System.out.println("Define the subsets...");

        System.out.println("Subset 2, enter the size");

        int size2=sc.nextInt();

        int arr2[]=new int[size2];

        for(int i=0;i<size2;i++){
            System.out.println("Enter the node");
            int node=sc.nextInt();
            arr2[i]=node;
        }

        int difference;
        difference=bfs(list,arr1,arr2);
        

        System.out.println("The difference is:"+difference);
    }
}