3.2 Par cours des graphes
77
© Dunod – Toute reproduction non autorisée est un délit.
fin de la seconde passe
Ici on a ouvert
D puis G, puis
fermé C, D, G, J, K.
ici on a ouvert
N puis O, puis
fermé O, N, et M.
Début de la troisième passe
Fin de la troisième passe
Figure 3.17 En traits gras : on a obtenu, en fin du parcours, une forêt couvrante.
Nous allons mon trer, dans les exemples qui suivent, comment des algo rithmes de
parcours des graphes peuvent uti li ser les posi tions rela tives des som mets dans ces
deux ordres et la forêt cou vrante (défi nie pré cé dem ment), pour déter mi ner effi ca ce ­
ment cer taines pro prié tés et/ou quan ti tés carac té ris tiques du graphe par couru.
Connexité d’un graphe
Le pro blème de la connexité consiste à déter mi ner si le graphe donné est connexe et
sinon à déterminer p, le nombre de compo santes connexes du graphe. Si le graphe n’est
pas connexe (c’est- à-dire, p > 2), il est demandé de déter mi ner, pour chaque som met
du graphe, la compo sante connexe à laquelle il appar tient. Ce pro blème peut se for mu ler
pour les graphes non orien tés ou orien tés : dans ce der nier cas, un arc est assi milé à une
arête et deux arcs symé triques (x, y) et (y, x) sont fusion nés en une seule arête [x, y].
Nous mon trons qu’une simple adap ta tion de l’algo rithme de par cours donné plus
haut résout ce pro blème. On note c(x) le numéro de la compo sante connexe à laquelle appar tient le som met x.
Consi dé rons l’algo rithme sui vant (le lec teur consta tera qu’il est simi laire à celui
pré senté plus haut) :
1. ini tia le ment tous les som mets sont non mar qués ; p d 0 ;
2. tant qu’il existe s un som met non mar qué, ouvrir s ; p d p 1 1 ;