En informatique, et plus particulièrement en génie logiciel, le type abstrait graphe est la spécification formelle[1] des données qui définissent l'objet mathématique graphe[2] et de l'ensemble des opérations qu'on peut effectuer sur elles. On qualifie d'« abstrait » ce type de données car il correspond à un cahier des charges qu'une structure de données concrète doit ensuite implémenter.
La structure de données abstraite de graphes consiste en un ensemble fini, éventuellement mutable de sommets ou nœuds ou points, avec un ensemble de paires ordonnées ou non de tels éléments Ces paires sont des arêtes, arcs non orientés, ou lignes pour un graphe non orienté, et flèches, arêtes orientées , arcs, ou lignes orientées dans le cas orienté. Les sommets peuvent faire partie de la structure, ou être des entités extérieures, représentées par des entiers ou des références.
Une structure de graphe peut aussi associer, à chaque arête, une « valeur », telle qu'une étiquette ou une valeur numérique (un coût, une capacité, une longueur, etc.). Plus généralement, un graphe peut aussi être donnée par deux ensembles d'objets, un de sommets et un ensemble d'arêtes, muni de deux applications qui, à chaque arête, associent son sommet de départ et son sommet d'arrivée. Cette vision[3] permet d'associer des valeurs à chaque objet (sommet ou arête).
Les opérations de base fournies par une structure de données de graphe G incluent usuellement[4],[3] :
sont_adjacents
(G, x, y): teste s'il y a une arête de x à y;voisins
(G, x): liste les sommets qui sont adjacents à x;ajouter_sommet
(G, x): ajoute le sommet x s'il n'y figure pas déjà;supprimer_sommet
(G, x): supprime le sommet x s'il existe;ajouter_arête
(G, x, y): ajoute l'arête de x à y s'il n'y figure pas déjà;supprimer_arête
(G, x, y): supprime l’arête de x à y si elle existe;retourner_valeur_sommet
(G, x): retourne la valeur associée à x;fixer_valeur_sommet
(G, x, v): fixe la valeur de x à v.Les structures qui associent des valeurs aux arêtes disposent en général[4] des opérations suivantes :
retourner_valeur_arête
(G, x, y): retourne la valeur de l'arête (x, y);fixer_valeur_arête
(G, x, y, v): fixe à v la valeur de l’arête (x, y).Diverses structures de données sont utilisées en pratique pour la représentation de graphes :
La table suivante donne la complexité en temps des diverses opérations sur les graphes selon les représentations. Ici est le nombre de sommets et le nombre d'arêtes.
Liste d'ajacence | Matrice d'adjacence | Matrice d'incidence | |
---|---|---|---|
Créer le graphe | |||
Ajouter un sommet | |||
Ajouter une arête | |||
Supprimer un sommet | |||
Supprimer une arête | |||
Test d'adjacence entre deux sommets | |||
Remarques | Lent dans la suppression parce qu'il faut trouver les sommets ou arêtes | Lent dans l'adjonction ou suppression de sommets parce que la matrice doit être reformatée | Lent dans l'adjonction ou suppression de sommets ou d'arêtes parce que la matrice doit être reformatée |
Les listes d'adjacence sont en général préférables pour des graphes peu denses. Une matrice d'adjacence est au contraire préférable quand le graphe est dense, c'est-à-dire quand le nombre d'arêtes |E | est proche du carré du nombre de sommets |V |2, mais aussi lorsque l'on veut savoir rapidement tester l'existence d'une arête entre deux sommets[10],[11],[3].