/*
* 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 Prim;
import java.util.Random;
import java.util.Scanner;
/**
*
* @author Boka
*/
public class Prim {
static int n=0,i,j;
static int m [][];
static int min=33;
static arret tab[];
public static void main(String[] args) {
Random rand =new Random();
Scanner sc =new Scanner(System.in);
n=sc.nextInt(); // nomber de sommet
System.out.println("le nomber de sommet sont : "+n);
m =new int [n][n];
int min=9999,u=0,v = 0;
System.out.println("la matrice sont :");
for( i=0;i<n;i++){
for(j=i+1;j<n;j++){ // la valeur de j sont i+1 par ce que nous avons
m[i][j]=Math.abs( rand.nextInt(10)); // remplir la matrice avec des valeurs entre 0 et 9
if(m[i][j]==0){
m[i][j]=33;
}
} }
// l' afichage de la matrice
for( i=0;i<n;i++){
for(j=0;j<n;j++){
m[j][i]=m[i][j];
System.out.print(" "+m[i][j]);
}
System.out.println();
}
//on peut choisir un sommet de début aleatoir et remplacer les 0 avec 33
int debut =Math.abs(rand.nextInt(n));
System.out.println("la sommet initial est :"+debut);
int select[]=new int [n];
for(i=0;i<n;i++){
select[i]=0;
for(j=0;j<n;j++)
{
if(m[i][j]==0){
m[i][j]=33;
}
}
}
// la table des arretes
tab =new arret[100];
int c =0;
// remplir la table (c'est pas la matrice) des arretes
for(i=0;i<n;i++){
for(j=0;j<n;j++){
tab[c]=new arret(i,j,m[i][j]);
c++;
}}
int tabA[]=new int[100];
int w=0;
try{
for(i=0;i<100;i++){
tab[i].affiche_arret(i);
}
}catch(Exception e){}
// tous les cellules de table avec 0 sauf le sommet de debut avec 1
//la 1ere boucle verfifier que le sommet choisier si le sommet de debut
// la 2eme boucle pour eviter les cyrcles
//et la 3eme boucle pour l'echange
select[debut]=1;
int total=0;
for( int conteur = 0; conteur <n-1 ; conteur++){
min = 10;
for(int i = 0; i < n; i++){
if(select[i]==1){
for(int j = 0; j < n; j++){
if(select[j]==0){
if(m[i][j] < min){
min = m[i][j];
u = i;
v = j;
}
}}
}
}
select[v] = 1;
total += min;
System.out.println("l'ensemble est "+"{"+u+","+v+"}");
System.out.println("("+u+") --> "+"("+v+")"+" : "+min);
// System.out.println("("+(tab[i].get_x())+")"+" --> "+"("+(tab[i].get_y())+")"+" = "+min);
}
System.out.println("les arrets rest apres l'utilisation de prim sont "+ total);
}
}
