3.2 Par cours des graphes
79
© Dunod – Toute reproduction non autorisée est un délit.
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 ;
3. tant que cela est pos sible, exé cu ter l’une des ins truc tions 4 ou 5 ;
4.
ouvrir un som met y non mar qué s’il est suc ces seur d’un som met x ouvert ;
5.
fer mer un som met x si tous ses som mets suc ces seurs sont ouverts ou fer més.
Les figures 3.20 et 3.21 illus trent un dérou le ment pos sible de l’algo rithme pour le
le graphe repré senté sur la figure 3.19.
Figure 3.19
Les étapes suc ces sives du par cours sont les sui vantes. A est le pre mier som met
ouvert, puis vient ensuite l’ouver ture de B, sui vie de celle de G. À l’étape sui vante,
F est ouvert lors de la pour suite de la visite du som met B, ce qui jus ti fie l’intro duc
tion de l’arc (B, F) dans la forêt repré sen ta tive du par cours. Ensuite, le som met A est
fermé, puis le som met D est ouvert. Les som mets B et G sont suc ces si ve ment fer més
avant que C soit ouvert. Il vient ensuite les fer me tures suc ces sives des som mets D,
C et F. À cette étape, aucun som met n’est ouvert et le som met E est encore non mar -
qué. E est alors ouvert, puis n’ayant pas de successeur non marqué, E est fermé. Le
par cours est alors ter miné.
La forêt fina le ment obte nue est repré sen té par l’ensemble des arcs épais du graphe
au bas à droite de la figure 3.21. Elle comporte deux arborescences ; celle de racine
E est réduite à une seul sommet.
L’ordre dans lequel les som mets du graphe sont ouverts, cor res pond à la liste :
PRÉVISITE 5 (A, B, G, F, D, C, E)
et l’ordre de postvisite cor res pond à la liste
POSTVISITE 5 (A, B, G, D, C, F, E).
Nous allons mon trer, dans le para graphe sui vant, comment en adap tant très sim -
ple ment l’algo rithme géné rique que nous venons de pré sen ter, nous obte nons un
algo rithme effi cace per met tant de déter mi ner l’ensemble des des cen dants d’un som
met donné. Le lec teur est invité à consta ter que l’algo rithme de Dijkstra, pré senté au
cha pitre 4, qui cal cule les valeurs de plus courts che mins issus d’une ori gine s, est
un par cours de graphe uti li sant une stra té gie spé ci fique d’ouver ture et de fer me ture
des som mets.
79
© Dunod – Toute reproduction non autorisée est un délit.
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 ;
3. tant que cela est pos sible, exé cu ter l’une des ins truc tions 4 ou 5 ;
4.
ouvrir un som met y non mar qué s’il est suc ces seur d’un som met x ouvert ;
5.
fer mer un som met x si tous ses som mets suc ces seurs sont ouverts ou fer més.
Les figures 3.20 et 3.21 illus trent un dérou le ment pos sible de l’algo rithme pour le
le graphe repré senté sur la figure 3.19.
Figure 3.19
Les étapes suc ces sives du par cours sont les sui vantes. A est le pre mier som met
ouvert, puis vient ensuite l’ouver ture de B, sui vie de celle de G. À l’étape sui vante,
F est ouvert lors de la pour suite de la visite du som met B, ce qui jus ti fie l’intro duc
tion de l’arc (B, F) dans la forêt repré sen ta tive du par cours. Ensuite, le som met A est
fermé, puis le som met D est ouvert. Les som mets B et G sont suc ces si ve ment fer més
avant que C soit ouvert. Il vient ensuite les fer me tures suc ces sives des som mets D,
C et F. À cette étape, aucun som met n’est ouvert et le som met E est encore non mar -
qué. E est alors ouvert, puis n’ayant pas de successeur non marqué, E est fermé. Le
par cours est alors ter miné.
La forêt fina le ment obte nue est repré sen té par l’ensemble des arcs épais du graphe
au bas à droite de la figure 3.21. Elle comporte deux arborescences ; celle de racine
E est réduite à une seul sommet.
L’ordre dans lequel les som mets du graphe sont ouverts, cor res pond à la liste :
PRÉVISITE 5 (A, B, G, F, D, C, E)
et l’ordre de postvisite cor res pond à la liste
POSTVISITE 5 (A, B, G, D, C, F, E).
Nous allons mon trer, dans le para graphe sui vant, comment en adap tant très sim -
ple ment l’algo rithme géné rique que nous venons de pré sen ter, nous obte nons un
algo rithme effi cace per met tant de déter mi ner l’ensemble des des cen dants d’un som
met donné. Le lec teur est invité à consta ter que l’algo rithme de Dijkstra, pré senté au
cha pitre 4, qui cal cule les valeurs de plus courts che mins issus d’une ori gine s, est
un par cours de graphe uti li sant une stra té gie spé ci fique d’ouver ture et de fer me ture
des som mets.