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 MG 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 :
MG[
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|
2 é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];
}
// ...
}