Prims

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package LAB4_Prims;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Scanner;


public class prims {
    public static int node;
    public static int [][] matrix;
    public static int [] color;
    public static int [] parent;
    public static int [] vertices= {0,1,2,3,4,5,6,7,8};
    public static int [] d;

    public static PriorityQueue<Integer> q = new PriorityQueue<Integer>();



    public static void main(String [] args) {
     try{
            Scanner scn=new Scanner(new File("E://Ins.txt"));
            String[] splitA;

            String temp=scn.nextLine();
            node=Integer.parseInt(temp);


         String temp1=scn.nextLine();
            int edge=Integer.parseInt(temp1);


         //   out.println(v);
            matrix=new int[node][node];
            color=new int[node];
            parent=new int[node];
            d=new int[node];
            while(scn.hasNext())
            {
            String line=scn.nextLine();
            splitA=line.split(",");
            int x=Integer.parseInt(splitA[0]);
            int y=Integer.parseInt(splitA[1]);
            int w=Integer.parseInt(splitA[2]);
            matrix[x][y]=w;
            matrix[y][x]=w;
            }
         for(int i=0;i<node;i++) {
                for(int j=0;j<node;j++) {
                    System.out.print(matrix[i][j]+",");
                }
                System.out.println();
            }

         color=new int[node];
         HashSet<Integer> Set=new <Integer>HashSet();

         int s=0;

         for(int i=0;i<node;i++){
             if(i!=s){
                 color[i]=0;
           d[i]=999;
           parent[i]=-1;

         }
         }

         for(int i=0;i<node;i++){

           q.add(d[i]);
         }
         for(int i:d){
             System.out.print(i+" ");
         }

         d[s]=0;
         parent[s]=-1;
         color[s]=1;
         //q.add(d[s]);
         while(!(q.isEmpty())){
             //System.out.println("sssssssssssss");
             //System.out.println(q.peek()+"");

             int u=findIndex(q.poll(),d);
             //System.out.println(u+"<<<>>>");
             for(int v=0;v<node;v++){
                 if(matrix[u][v]!=0){

                     if(matrix[u][v]<d[v]){
                         parent[v]=u;
                         d[v]=matrix[u][v];
                     }
                 }
             }
             color[u]=1;//black
                queueSort();
                if(q.peek()!=null){
                System.out.print(u+"->");
                }else{
                    System.out.print(u);
                }

         }
         for(int i:d){
             System.out.print(i+" ");
         }



         }
     catch(Exception e){
         e.printStackTrace();
     }
    }
     public static int findIndex(int value,int [] arr) {
         int index=-1;
         for(int i=0;i<arr.length;i++){
             if(value==arr[i] ){
                 index=i;
             }
         }
        return index;
    }

      public static void queueSort(){
        q.clear();
        for(int i=0;i<node;i++){
            if(color[i]==0){
            q.add(d[i]);

        }
       }

    }
}