Cahier des charges
Dans cet exemple, nous voulons étudier deux façons de
coder un graphe orienté par la matrice dite d'adjacence, ou par un
tableau indiquant, pour chaque sommet, la liste chaînée de ses
fils. Dans le cas de la matrice d'adjacence, on distinguera
deux façons de faire : définir la matrice d'adjacence de
façon statique en "surdimenssionnant" celle-ci, ou bien allouer
dynamiquement l'espace mémoire nécessaire à cette
matrice.
Nous allons séparer ces trois possibilités en examinant successivement trois petits programmes.
Les cahiers des charges de ces trois programmes sont identiques :
- saisir le graphe (en le "rentrant" dans la structure correspondante)
en utilisant un fichier de lecture, appelé "graphe.don",
- afficher à l'écran l'ordre du graphe et, pour chaque
sommet, la liste de ses fils.
Les sommets du graphe sont des entiers consécutifs, le premier étant 0.
Dans le fichier "graphe.don", on trouve l'ordre du graphe et la liste
des arcs du graphe : origine d'un arc, extrémité de ce même arc, origine d'un autre arc, etc.
La matrice d'adjacence d'un graphe est une matrice carrée dont les deux dimensions sont égales à l'ordre du graphe. Si i et j
sont deux numéros de sommets, la matrice contient en
coordonnées (i,j) : 1 s'il existe un arc d'origine i et
d'extrémité jet 0 sinon.
Vous pouvez, si vous le voulez, commencer par visualiser, à
titre d'exemple, le fichier "graphe.don"
que peuvent utiliser nos trois
programmes ci-dessous étudiés.
en cliquant sur son nom.
Choisissez le codage que vous voulez étudié>
Nous vous conseillons maintenant de faire les exercices ci-dessous.