Représentations et implémentations des graphes
Représentations versus implémentations
Nous allons distinguer ici les représentations des graphes de leur implémentation.
La représentation d'un graphe consiste à décrire le graphe avec des objets et des opérateurs qui permettent de travailler sur ce graphe : opérateurs d'accès à une valeur ou à sa modification, opérateur d'exploration ou de défilement des objets dans une liste... Ces objets et ces opérateurs sont utilisés dans la description générique des algorithmes.
L'implémentation de la représentation d'un graphe concerne essentiellement les informaticiens qui programment les classes ou les fonctions ou les sous-programmes qui vont permettre de réaliser effectivement les algorithmes qui ont été décrits en utilisant les objets et les opérateurs associés à un type de représentation.
Attention :
Pour ce cours de base, vous pouvez vous contentez de la notion de représentation des graphes.
Tout le module est compréhensible en se contentant de cette notion.
Toute personne, qui n'est pas dans un cursus informatique et/ou qui n'aura jamais à programmer effectivement des algorithmes de graphe et/ou qui n'est pas intéressée par les problèmes d'implémentation, mais qui cherche simplement à comprendre le fonctionnement global des algorithmes, peut sauter dans toute cette partie les paragraphes qui comportent dans leur titre le mot "implémentation".
Utilité de distinguer les notions de représentation et d'implémentation
Le choix de la représentation permet d'écrire plus ou moins simplement les algorithmes.
La complexité de l'algorithme dépend déjà de la représentation utilisée.
Le choix de la représentation dépend également de la famille particulière de graphes considérée. Par exemple, les forêts ou les graphes bi-partis bénéficient de représentation simplifiée et adaptée à la famille particulière.
Le choix de l'implémentation de la représentation peut dépendre des données numériques associées aux exemples concrets que l'on traite avec l'algorithme. Par exemple, on sait que, pour le problème concret que l'on traite, le graphe est très pauvre (graphe peu dense) ou très riche (graphe dense) en arcs.
Avoir des statistiques sur la structure des graphes sur lesquels on va travailler permet d'optimiser l'occupation mémoire et/ou la durée des algorithmes. Cette optimisation peut passer par le choix de l'algorithme de résolution et des représentations des graphes associées, mais également par le choix de l'implémentation de ces représentations.
Remarque :
Compte tenu de l'évolution des ordinateurs, de leur rapidité de plus en plus grande et du coût devenu de plus en plus faible de la mémoire, l'optimisation de la place mémoire utilisée par les implémentations a de moins en moins d'importance, par contre l'optimisation de la durée de l'algorithme reste très importante lorsque les algorithmes sont "exponentiels" (durée en O(ap), où p est associé à une des dimensions du graphe, par exemple nombre de sommets ou nombre d'arcs ou une combinaison des deux).
