/*Specifications :
L'algorithme de Kruskal traite du probleme de l'arbre couvrant de poids
minimum.
On considere un graphe dont les sommets sont des entiers consecutifs, 
le plus petit d'entre eux etant le sommet 0. Le graphe n'est pas 
necesairement complet, les poids sont des "flottants".
Pour resoudre le probleme :
- on saisit le graphe arete par arete, en faisant correspondre a chaque 
arete une structure contenant les noms des deux extremites de l'arete et 
son poids ;
- on trie le tableau ainsi obtenu par poids croissants (par le tri insertion);
- on construit au fur et a mesure l'arbre en partant de l'ensemble des sommets
et d'un ensemble vide d'aretes. On numerote les sommets pour que, au fur et 
a mesure de l'algorithme, deux sommets aient meme numero si et seulement 
s'ils appartiennent a une meme compsante connexe de l'arbre en construction. 
Pour cela, on attribue au depart le numero i au sommet i. On ajoute a l'arbre 
les aretes en suivant le tableau trie mais en "sautant" les aretes dont les 
extremites ont meme numero (qui appartiennent donc a une meme composante 
connnexe). Lorsqu'on ajoute une arete, on note num1 et num2
les numeros de ses extremites : tout sommet ayant comme numero num2 
voit changer son numero en num1.
	L'ordre, la taille, la liste des aretes et de leurs poids 
seront lus dans un fichier. On demandera a l'utilisateur de donner le 
nom de ce fichier. Les resultats seront affiches a l'ecran et aussi 
sauvegardes dans un fichier dont on demandera le nom a l'utilisateur.
	Les seules variables globales seront l'ordre et la taille du graphe.
	Les tableaux seront alloues dynamiquement.
	Enfin, on detectera le cas ou le graphe n'est pas connexe 
(auquel cas le probleme n'a pas de solution), et on indiquera cela 
uniquement a l'ecran*/

#include <stdio.h>
#include <stdlib.h>

typedef struct arete
{
  int extr1, extr2;
  float poids;
}Arete;

int ordre, taille;

Arete * SaisirGraphe(void);
void TrierGraphe(Arete *);
Arete * ConstruireArbre(Arete *);
void AfficherSauverArbre(Arete *);

void main()
{
  Arete * graphe, * arbre;
  
  graphe = SaisirGraphe();
  TrierGraphe(graphe);
  arbre=ConstruireArbre(graphe);
  AfficherSauverArbre(arbre);
}

Arete *  SaisirGraphe()
{
  FILE * fichier;
  char nom[20];
  int i;
  Arete * LeGraphe;
  
  printf("Quel est le nom du fichier d'entree ?\n");
  gets(nom);
  
  /* A COMPLETER ; prevoir le cas ou le fichier n'existerait pas*/
  
  return LeGraphe;
}

void TrierGraphe(Arete * graphe)
{
  int i,j;
  Arete cle;
  
  for (i=1;i<taille;i++)
    {
      cle=graphe[i];
      for (j=i-1;((j>=0)&&(cle.poids<graphe[j].poids));j--) 
	graphe[j+1]=graphe[j];
      graphe[j+1]=cle;
    }
}

Arete * ConstruireArbre(Arete * UnGraphe)
{
  int * NumComp;
  Arete * LArbre;
  int sommet;
  /* A COMPLETER */
  
  NumComp=(int *) malloc(ordre*sizeof(int));
  for (sommet=0;sommet<ordre;sommet++) NumComp[sommet]=sommet;
  
  /* A COMPLETER */
  return LArbre;
}


void AfficherSauverArbre(Arete * UnArbre)
{
  int i;
  FILE * fichier;
  char nom[20];
  
  printf("Voici les aretes de l'arbre couvrant de poids minimum :\n");
  for (i=0;i<ordre-1;i++)
    printf("%d %d\n", UnArbre[i].extr1,UnArbre[i].extr2);
  printf("Quel est le nom du fichier de sortie ? ");
  gets(nom);
  
  /* A COMPLETER pour que la sortie soit aussi sur fichier*/
}