Code source

arbre PRIM( graphe ({1, 2, ..., n}, A, v) ) {
T ¬  {1} ;
B ¬  Æ ;
tant que card T < n faire {
{p, q} ¬ arête de coût minimal
telle que p Î T et q Ï T ;
T ¬ T + {q} ;
B ¬  B + {p, q} ;
}
retour (T, B) ;
}
Temps d’exécution : O(n²) au moyen de deux tables
indexées par les sommets
Algorithme de Prim

arbre KRUSKAL( graphe ({1, 2, ..., n}, A, v) ) {
Partition ¬ { {1}, {2}, ..., {n} } ;
B ¬  Æ ;
tant que card Partition > 1 faire {
{p, q} ¬ arête de coût minimal telle que
CLASSE(p) ¹ CLASSE(q) ;
B ¬  B + {p, q} ;
remplacer dans Partition CLASSE(p) et
CLASSE(q) par leur UNION ;
}
retour ( ({1, 2, ..., n}, B ) ;
}
Temps d’exécution : O(card A.log card A) avec gestion
efficace de la partition : type abstrait CLASSE-UNION

public class Arete
{  private int sommet1, sommet2;
   private double cout;
   
   public Arete(int sommet1, int sommet2, double cout)
   {  this.sommet1 = sommet1;
      this.sommet2 = sommet2;
      this.cout = cout;
   }

   public int getSommet1()
   {  return sommet1;
   }
   
   public int getSommet2()
   {  return sommet2;
   }
   
   public double getCout()
   {  return cout;
   }
}

import java.util.*;
import java.io.*;

public class Graphe
{  private int n; // nombre de sommets
   private boolean adj[][]; // matrice d'adjacence
   private double dist[][]; // co�ts des ar�tes
   
   
   public Graphe(int n)
   {  this.n = n;
      adj = new boolean[n][n];
      dist = new double[n][n];
   }
 
   public Graphe(String nomFichier) throws IOException
   {  StreamTokenizer st =
         new StreamTokenizer(new BufferedReader(new FileReader(nomFichier)));
      st.nextToken();
      int n = (int)st.nval;
      this.n = n;
      adj = new boolean[n][n];
      dist = new double[n][n];
      st.nextToken();
      int m = (int)st.nval;
      
      int s1, s2;
      double cout;
      for (int j = 0; j < m; j++)
      {  st.nextToken();
         s1 = (int)st.nval;
	 st.nextToken();
	 s2 = (int)st.nval;
	 st.nextToken();
	 cout = st.nval;
	 ajouterArete(s1, s2, cout);
      }
   }
   
   public int nbSommets()
   {  return n;
   }
   
   public void ajouterArete(int sommet1, int sommet2, double cout)
   {  adj[sommet1][sommet2] = adj[sommet2][sommet1] = true;
      dist[sommet1][sommet2] = dist[sommet2][sommet1] = cout;
   }
   
   public void ajouterArete(Arete a)
   {  ajouterArete(a.getSommet1(), a.getSommet2(), a.getCout());
   }
   
   public void supprimerArete(int sommet1, int sommet2)
   {  adj[sommet1][sommet2] = adj[sommet2][sommet1] = false;
   }
   
   public void supprimerArete(Arete a)
   {  supprimerArete(a.getSommet1(), a.getSommet2());
   }
   
   public double distanceEntre(int sommet1, int sommet2)
   {  return adj[sommet1][sommet2] ? dist[sommet1][sommet2] : Double.MAX_VALUE;
   }
   
   public int[] voisinsDe(int sommet)
   {  int nb = 0;
      for (int i = 0; i < n; i++)
         if (adj[sommet][i]) nb++;
      int[] v = new int[nb];
      nb = 0;
      for (int i = 0; i < n; i++)
         if (adj[sommet][i]) v[nb++] = i;
      return v;
   }
   
   public Arete[] aretes()
   {  ArrayList a = new ArrayList();
      for (int i = 0; i < n; i++)
         for (int j = i + 1; j < n; j++)
	    if (adj[i][j]) a.add(new Arete(i, j, dist[i][j]));
      return (Arete[])a.toArray(new Arete[0]);
   }
   
   public boolean sontVoisins(int sommet1, int sommet2)
   {  return adj[sommet1][sommet2];
   }
}

import java.io.*;
import java.util.*;

class MonComparator implements Comparator
{  public int compare(Object o1, Object o2)
   {  double d1 = ((Arete)o1).getCout();
      double d2 = ((Arete)o2).getCout();
      if (d1 < d2) return -1;
      if (d1 > d2) return 1;
      return 0;
   }
}


public class AlgoKruskal
{  public static Graphe arbreCouvrant(Graphe g)
   {  int n = g.nbSommets();
      Graphe ac = new Graphe(n);
      
      Arete[] a = g.aretes();
      Arrays.sort(a, new MonComparator());
      int[] compConnexe = new int[n];
      for (int i = 0; i < n; i++)
         compConnexe[i] = i;
	 
      int k = 0;
      int j = 0;     
      while (k < n - 1)
      {  int u = a[j].getSommet1();
         int v = a[j].getSommet2();
	 if (compConnexe[u] != compConnexe[v])
	 {  k++;
	    ac.ajouterArete(a[j]);
	    int aux = compConnexe[v];
	    for (int i = 0; i < n; i++)
	       if (compConnexe[i] == aux)
	          compConnexe[i] = compConnexe[u];
         }
	 j++;
      }
      return ac;
   }
   
   
   public static void main(String[] args)
   {  Graphe g;
   
      try
      {  g = new Graphe(args[0]);
      }
      catch (IOException e)
      {  System.err.println("Erreur de lecture du fichier " + args[0]);
         return;
      }
      
      Graphe ac = arbreCouvrant(g);
      Arete[] a = ac.aretes();
      double coutTotal = 0;
      for (int j = 0; j < a.length; j++)
      {  System.out.println(a[j].getSommet1() + " " + a[j].getSommet2());
         coutTotal += a[j].getCout();
      }
      System.out.println(coutTotal);
   }
}