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 ), dont les éléments indiquent l'existence d'un arc : M_G[u][v] est différent de null si et seulement si . 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  d'un sommet u est l'ensemble L_G[u] des arcs . 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();
  }
  // ...
}