Implémentation des graphes

Deux implémentations des graphes sont couramment utilisées ; le choix se fait en fonction des opérations que l'on veut faire, et de la densité du graphe, c'est-à-dire du rapport entre le nombre d'arcs et le nombre de sommets.

La matrice d'adjacence  M_G d'un graphe G est une matrice carrée, indicée par les sommets (donc de dimension $\vert S\vert\times\vert S\vert$), dont les éléments indiquent l'existence d'un arc : M_G[u][v] est différent de null si et seulement si $u\to v$. La représentation d'un graphe par sa matrice d'adjacence est préférée quand le graphe est dense (beaucoup d'arcs), car elle comporte toujours les |S|² éléments d'un tableau bidimensionnel ; elle est bien adaptée aux algorithmes qui s'expriment à l'aide d'opérations matricielles.

public class GrapheParMatrice implements Graphe {
  private Arc[][] adjacence;

  public GrapheParMatrice(int taille) {
    adjacence = new boolean[taille][taille];
  }
  // ...
}

L'ensemble d'adjacence ^2.1 d'un sommet uest l'ensemble L_G[u] des arcs $u\to v$. Un graphe Gest défini par l'association, à chaque sommet u de son ensemble d'adjacence L_G[u]. Cette représentation est préférée quand le graphe est creux (peu d'arcs).

public class GrapheParListe implements Graphe {
  private Set[] adjacence;

  public GrapheParListe(int taille) {
    adjacence = new HashSet[taille];
    for (int i = 0; i < taille; i++)
      adjacence[i] = new HashSet();
  }
  // ...
}