/* ====================================================================== */
/*! \fn graphe * Kruskal1(graphe * g)
    \param g (entrée) : un graphe pondéré connexe antisymétrique antiréflexif
    \return un arbre
    \brief retourne un arbre de poids maximal pour g
*/
graphe * Kruskal1(graphe * g)
/* ====================================================================== */
{
  int n = g->nsom;
  int m = g->narc;
  graphe * apm;    /* pour le résultat */
  graphe * apm_1;  /* symétrique de apm, nécessaire pour la détection de cycles */
  int *A;          /* tableau pour ranger les index des arcs */
  int i, j, t, q;
  boolean *Ct = EnsembleVide(n);

  /* tri des arcs par poids croissant */
  A = (int *)malloc(m * sizeof(int)); /* allocation index */
  if (A == NULL)
  {   fprintf(stderr, "Kruskal1 : malloc failed\n");
      exit(0);
  }  
  for (i = 0; i < m; i++) A[i] = i; /* indexation initiale */
  TriRapideStochastique(A, g->v_arcs, 0, m-1);

  /* construit le graphe resultat, initialement vide */
  apm = InitGraphe(n, n-1);
  apm_1 = InitGraphe(n, n-1);

  /* Boucle sur les arcs pris par ordre decroissant:
       on ajoute un arc dans apm, si cela ne cree pas un cycle dans apm.
     Arret lorsque nb arcs ajoutes = n-1. */

  j = 0; 
  i = m - 1;
  while (j < n-1)
  {
    t = g->tete[A[i]]; q = g->queue[A[i]]; // arc (t,q)
    CompConnexe(apm, apm_1, t, Ct); // Ct = composante connexe contenant t
    if (!Ct[q]) // q n'est pas dans Ct : on ne va pas creer de cycle !
    {
      AjouteArc(apm, t, q);
      AjouteArc(apm_1, q, t);
      j++; 
    }
    i--;
    if (i < 0)
    {   fprintf(stderr, "Kruskal1 : graphe d'origine non connexe\n");
        exit(0);
    }  
  }

  if (g->x != NULL) // recopie les coordonnees des sommets pour l'affichage
    for (i = 0; i < n; i++) { apm->x[i] = g->x[i];  apm->y[i] = g->y[i]; }

  free(A);
  free(Ct);
  TermineGraphe(apm_1);
  return apm;
} /* Kruskal1() */