3.2 Par cours des graphes
71
© Dunod – Toute reproduction non autorisée est un délit.
pour suit sa visite. Lors qu’il n’est plus pos sible de pour suivre la visite d’aucun som -
met du graphe, pour le som met ini tial choisi, la pro cé dure s’arrête si tous les som -
mets du graphe sont visi tés ; dans le cas contraire, on reprend le par cours à par tir
d’un som met non encore visité.
Tout au long de la pro cé dure de par cours d’un graphe, chaque som met passe par trois
états suc ces sifs : ini tia le ment, un som met n’est pas atteint par le par cours, il est alors dit
non mar qué, puis lors qu’un som met est atteint pour la pre mière fois, sa visite débute, le
som met est alors dans l’état ouvert, enfin lorsque la visite d’un som met est ter mi née, le
som met est alors dans l’état fermé. Un par cours débute alors par l’ouver ture d’un som -
met du graphe (le som met ini tial) et se ter mine lorsque tous les som mets sont fer més.
Les algo rithmes effec tuant des par cours de graphe se dis tinguent par la stratégie
de choix, à chaque étape, du som met à ouvrir, à par tir duquel est pour sui vie la visite.
Ainsi la stra té gie uti li sée par un algo rithme de par cours induit deux ordres pour les
som mets du graphe :
• l’ordre dans lequel les som mets sont ouverts, appelé ordre de prévisite ;
• l’ordre dans lequel les som mets sont fer més, appelé ordre de postvisite.
La complexité algo rith mique du par cours d’un graphe dépend du type de stra -
té gie uti li sée. Cepen dant, dans un pre mier temps, si l’on sup pose que le choix du
som met à ouvrir à chaque étape peut se faire en un temps constant (c’est- à-dire avec
une complexité O(1), voir le cha pitre 2), la complexité du par cours est O(n 1 m). En
effet, si le graphe est repré senté sous la forme de listes de suc ces seurs (ou bien de
listes de som mets adja cents pour un graphe non orienté) (cf. 3.1.2), cha cune des n
listes asso ciées aux n som mets du graphe est par cou rue entiè re ment une fois et une
seule. Cha cun des élé ments d’une liste cor res pon dant à l’un des m arcs (ou des m
arêtes) du graphe, nous en dédui sons la complexité annon cée.
Après avoir donné deux exemples de par cours dans les graphes orien tés et les graphes
non orien tés, nous consa cre rons les deux der nières par ties de ce sous-cha pitre à deux
stra té gies de par cours sur les quelles sont fon dés de nom breux algo rithmes : le par cours
en lar geur et le par cours en pro fon deur. Nous ver rons qu’en uti li sant des struc tures de
don nées appro priées, ces deux der niers types de par cours ont une complexité O(n 1 m).
En R.O. on a souvent affaire à des graphes denses : m W n ; alors celle-ci est O(m).
3.2.1 Par cours d’un graphe non orienté
Dans ce para graphe, nous don nons un algo rithme géné rique effec tuant le par cours
d’un graphe non orienté. Nous allons voir ensuite, par l’inter mé diaire d’un exemple, comment un tel par cours per met de déter mi ner effi ca ce ment les compo santes
connexes d’un graphe. L’algo rithme est le sui vant :
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 adja cent à un som met x ouvert ;
5.
fer mer un som met x si tous ses som mets adja cents sont ouverts ou fer més.
71
© Dunod – Toute reproduction non autorisée est un délit.
pour suit sa visite. Lors qu’il n’est plus pos sible de pour suivre la visite d’aucun som -
met du graphe, pour le som met ini tial choisi, la pro cé dure s’arrête si tous les som -
mets du graphe sont visi tés ; dans le cas contraire, on reprend le par cours à par tir
d’un som met non encore visité.
Tout au long de la pro cé dure de par cours d’un graphe, chaque som met passe par trois
états suc ces sifs : ini tia le ment, un som met n’est pas atteint par le par cours, il est alors dit
non mar qué, puis lors qu’un som met est atteint pour la pre mière fois, sa visite débute, le
som met est alors dans l’état ouvert, enfin lorsque la visite d’un som met est ter mi née, le
som met est alors dans l’état fermé. Un par cours débute alors par l’ouver ture d’un som -
met du graphe (le som met ini tial) et se ter mine lorsque tous les som mets sont fer més.
Les algo rithmes effec tuant des par cours de graphe se dis tinguent par la stratégie
de choix, à chaque étape, du som met à ouvrir, à par tir duquel est pour sui vie la visite.
Ainsi la stra té gie uti li sée par un algo rithme de par cours induit deux ordres pour les
som mets du graphe :
• l’ordre dans lequel les som mets sont ouverts, appelé ordre de prévisite ;
• l’ordre dans lequel les som mets sont fer més, appelé ordre de postvisite.
La complexité algo rith mique du par cours d’un graphe dépend du type de stra -
té gie uti li sée. Cepen dant, dans un pre mier temps, si l’on sup pose que le choix du
som met à ouvrir à chaque étape peut se faire en un temps constant (c’est- à-dire avec
une complexité O(1), voir le cha pitre 2), la complexité du par cours est O(n 1 m). En
effet, si le graphe est repré senté sous la forme de listes de suc ces seurs (ou bien de
listes de som mets adja cents pour un graphe non orienté) (cf. 3.1.2), cha cune des n
listes asso ciées aux n som mets du graphe est par cou rue entiè re ment une fois et une
seule. Cha cun des élé ments d’une liste cor res pon dant à l’un des m arcs (ou des m
arêtes) du graphe, nous en dédui sons la complexité annon cée.
Après avoir donné deux exemples de par cours dans les graphes orien tés et les graphes
non orien tés, nous consa cre rons les deux der nières par ties de ce sous-cha pitre à deux
stra té gies de par cours sur les quelles sont fon dés de nom breux algo rithmes : le par cours
en lar geur et le par cours en pro fon deur. Nous ver rons qu’en uti li sant des struc tures de
don nées appro priées, ces deux der niers types de par cours ont une complexité O(n 1 m).
En R.O. on a souvent affaire à des graphes denses : m W n ; alors celle-ci est O(m).
3.2.1 Par cours d’un graphe non orienté
Dans ce para graphe, nous don nons un algo rithme géné rique effec tuant le par cours
d’un graphe non orienté. Nous allons voir ensuite, par l’inter mé diaire d’un exemple, comment un tel par cours per met de déter mi ner effi ca ce ment les compo santes
connexes d’un graphe. L’algo rithme est le sui vant :
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 adja cent à un som met x ouvert ;
5.
fer mer un som met x si tous ses som mets adja cents sont ouverts ou fer més.