3.2 Par cours des graphes
83
© Dunod – Toute reproduction non autorisée est un délit.
Une file est une liste ordon née d’élé ments pour laquelle seulement deux opé ra -
tions élé men taires peuvent être réa li sées : la pre mière opé ra tion sup prime le pre mier
élé ment en tête de la file ; la seconde insère un élé ment en queue de la file. Ces deux
opé ra tions peuvent s’effec tuer en temps constant en uti li sant une repré sen ta tion des
don nées appro priée (le lec teur pourra obte nir tous les détails tech niques néces saires en
consul tant les nom breux ouvrages trai tant d’algo rith mique et/ou de pro gram ma tion).
On n’a pas accès aux autres élé ments de la file. Par suite les deux ordres “PREVISITE”
(celui d’ouverture) et “POSTVISITE” (celui de fermeture) sont iden tiques.
TÊTE
QUEUE
L’algo rithme géné rique effec tuant le par cours en lar geur d’un graphe orienté
s’énonce de la manière sui vante :
1. ini tia le ment tous les som mets sont non mar qués ;
2. tant qu’il existe s un som met non mar qué, ouvrir s et insé rer s dans la file ;
3. tant que la file n’est pas vide faire ;
4.
sup pri mer le som met x en tête de la file ;
5.
ouvrir et insé rer suc ces si ve ment en queue la file tous les som mets y non mar -
qués, suc ces seurs de x ;
6.
fer mer le som met x.
La figure 3.22 en page suivante illustre le par cours en lar geur d’un graphe orienté
commençant par le sommet B. Pour cha cune des étapes de l’algo rithme, le contenu
de la file est repré senté sous le graphe cor res pon dant (la tête de file étant à gauche).
Plus courts che mins
Nous mon trons comment déter mi ner les plus courts che mins depuis le som met s et
les autres som mets d’un graphe. Nous rap pe lons que la lon gueur d’un che min est
le nombre d’arcs de ce che min ; il convient de la dis tin guer de la valeur d’un che -
min pour un graphe dont les arcs sont valués. Consi dé rons l’algo rithme sui vant (le
lec teur pourra consta ter sa simi li tude avec l’algo rithme pré senté plus haut), où d(x)
représente la longueur du chemin le plus court de s à x.
1. Ini tia le ment tous les som mets sont non mar qués ;
2. ouvrir s et insé rer s dans la file ; d(s) d 0 ;
3. tant que la file n’est pas vide faire ;
4.
sup pri mer le som met x en tête de la file ;
5.
ouvrir et insé rer suc ces si ve ment dans la file tous les som mets y non mar qués
suc ces seurs de x ;
d(y) d d(x) 1 1 ;
6.
fer mer le som met x.
La figure 3.23 (deux pages plus bas) illustre le dérou le ment de l’algo rithme à par tir du
som met s 5 A. Les valeurs ins crites à côté des som mets sont les lon gueurs des plus courts
che mins issus du som met A : ainsi les plus courts chemins de A à E comportent 3 arcs.
La jus ti fi cation de la vali dité de l’algo rithme se fait de la manière sui vante. Nous
allons mon trer que pour tout som met x du graphe, le che min de s à x dans l’arbo res cence
83
© Dunod – Toute reproduction non autorisée est un délit.
Une file est une liste ordon née d’élé ments pour laquelle seulement deux opé ra -
tions élé men taires peuvent être réa li sées : la pre mière opé ra tion sup prime le pre mier
élé ment en tête de la file ; la seconde insère un élé ment en queue de la file. Ces deux
opé ra tions peuvent s’effec tuer en temps constant en uti li sant une repré sen ta tion des
don nées appro priée (le lec teur pourra obte nir tous les détails tech niques néces saires en
consul tant les nom breux ouvrages trai tant d’algo rith mique et/ou de pro gram ma tion).
On n’a pas accès aux autres élé ments de la file. Par suite les deux ordres “PREVISITE”
(celui d’ouverture) et “POSTVISITE” (celui de fermeture) sont iden tiques.
TÊTE
QUEUE
L’algo rithme géné rique effec tuant le par cours en lar geur d’un graphe orienté
s’énonce de la manière sui vante :
1. ini tia le ment tous les som mets sont non mar qués ;
2. tant qu’il existe s un som met non mar qué, ouvrir s et insé rer s dans la file ;
3. tant que la file n’est pas vide faire ;
4.
sup pri mer le som met x en tête de la file ;
5.
ouvrir et insé rer suc ces si ve ment en queue la file tous les som mets y non mar -
qués, suc ces seurs de x ;
6.
fer mer le som met x.
La figure 3.22 en page suivante illustre le par cours en lar geur d’un graphe orienté
commençant par le sommet B. Pour cha cune des étapes de l’algo rithme, le contenu
de la file est repré senté sous le graphe cor res pon dant (la tête de file étant à gauche).
Plus courts che mins
Nous mon trons comment déter mi ner les plus courts che mins depuis le som met s et
les autres som mets d’un graphe. Nous rap pe lons que la lon gueur d’un che min est
le nombre d’arcs de ce che min ; il convient de la dis tin guer de la valeur d’un che -
min pour un graphe dont les arcs sont valués. Consi dé rons l’algo rithme sui vant (le
lec teur pourra consta ter sa simi li tude avec l’algo rithme pré senté plus haut), où d(x)
représente la longueur du chemin le plus court de s à x.
1. Ini tia le ment tous les som mets sont non mar qués ;
2. ouvrir s et insé rer s dans la file ; d(s) d 0 ;
3. tant que la file n’est pas vide faire ;
4.
sup pri mer le som met x en tête de la file ;
5.
ouvrir et insé rer suc ces si ve ment dans la file tous les som mets y non mar qués
suc ces seurs de x ;
d(y) d d(x) 1 1 ;
6.
fer mer le som met x.
La figure 3.23 (deux pages plus bas) illustre le dérou le ment de l’algo rithme à par tir du
som met s 5 A. Les valeurs ins crites à côté des som mets sont les lon gueurs des plus courts
che mins issus du som met A : ainsi les plus courts chemins de A à E comportent 3 arcs.
La jus ti fi cation de la vali dité de l’algo rithme se fait de la manière sui vante. Nous
allons mon trer que pour tout som met x du graphe, le che min de s à x dans l’arbo res cence