Représentation informatique d'un graphe


On s'intéresse ici à la représentation d'un graphe dans un programme informatique.

Il n'est bien évidemment pas possible de décrire tout ce qui est possible. Nous nous limiterons donc à l'utilisation de structures de données simples et présentes dans les langages algorithmiques classiques (C, C++, Pascal, ...).


On y parle donc de mises en œuvre classiques faisant usage :

- de tableaux

- de listes chaînées

- de structures de données de taille fixe ou dynamique


Ces structures de données peuvent bien entendu être encapsulées dans des constructeurs de "classes", pour les langages le permettant.


Ces techniques, initialement abordées pour des graphes non valués, sont étendues pour permettre la représentation de graphes valués.


Nous utilisons ici un "pseudo-langage" plutôt qu'un langage de programmation particulier. Ce pseudo-langage est cependant suffisamment proche de Pascal ou C pour qu'il soit compréhensible par tout le monde.