Chapitre 3 • Éléments de la théorie des graphes
82
che min de s à x existe dans l’arbo res cence rela tive au par cours seule ment si ce même
che min existe dans le graphe auquel l’algo rithme est appli qué ; d’autre part, s étant le
pre mier som met ouvert, il est aisé de véri fier que quelle que soit la manière dont le
par cours est réa lisé, tout som met des cen dant de s dans le graphe par couru est néces -
sai re ment un som met de l’arbo res cence ayant le som met s pour racine.
Dans ce cha pitre, nous avons donné dif fé rents algo rithmes per met tant de cal -
cu ler la fer me ture tran si tive d’un graphe. L’algo rithme le plus effi cace que nous
avions pré senté jus qu’alors était celui dû à Roy et Warshall de complexité O(n
3
).
L’algo rithme que nous venons de pré sen ter nous per met aussi d’obte nir la fer me ture
tran si tive d’un graphe. Il suf fit pour cela d’appli quer n fois cet algo rithme à par tir
de cha cun des n som mets du graphe. Comme nous le ver rons juste en des sous, il est
pos sible d’effec tuer le par cours d’un graphe avec une complexité O(n 1 m). Lorsque
le graphe consi déré comporte de nom breux arcs, c’est- à-dire m 5 O(n
2
), la complexité de ces par cours est O(n
2
), donc en effec tuant n par cours (un depuis chacun
des sommets) nous obte nons la fer me ture tran si tive d’un graphe avec la complexité
O(n
3
), ce qui est iden tique à la complexité de l’algo rithme de Roy- Warshall. En
revanche, si le graphe consi déré comporte peu d’arcs, c’est- à-dire m 5 O(n), ce qui
est le cas des graphes pla naires fré quem ment ren contrés en recherche opé ra tion nelle,
la complexité d’un par cours est alors O(m) 5 O(n). En effec tuant n par cours, nous
obte nons la fer me ture tran si tive d’un graphe avec une complexité O(n
2
). Pour ce
type de graphes, l’algo rithme effec tuant n par cours est alors plus effi cace que ceux
pré sen tés au début de ce cha pitre.
Tarjan a donné un algo rithme per met tant de résoudre le pro blème de l’acces si bi -
lité, de complexité O(m 1 n), utilisant un seul parcours du graphe.
3.2.3 Par cours en lar geur
Nous défi nis sons dans cette sec tion une stra té gie par ti cu lière de par cours de graphe
appe lée par cours en lar geur. Ce type de par cours est défini dans ce para graphe pour
les graphes orien tés, l’adap ta tion immé diate des algo rithmes, pro po sés ici, aux graphes non orien tés est lais sée au lec teur. Nous ver rons comment en uti li sant une file
comme struc ture de don nées, la complexité d’un algo rithme de par cours en lar geur
est O1 n 1 m 2 (nous rap pe lons plus bas en quoi consiste une file). Nous illus tre rons
ensuite l’effi ca cité des par cours en lar geur en mon trant comment déter mi ner les plus
courts che mins d’un graphe depuis un sommet s donné.
La stra té gie pour effec tuer un par cours en lar geur obéit aux deux règles sui -
vantes : tous les suc ces seurs non mar qués du som met en cours de visite sont
ouverts suc ces si ve ment et leurs numé ros d’ordre de prévisite seront donc consé cu -
tifs ; le som met visité à toute étape est, parmi les som mets ouverts, celui qui a été
ouvert le pre mier.
Comme nous l’avons mon tré un peu plus haut, si les opé ra tions per met tant de mettre
en œuvre une stra té gie par ti cu lière de par cours peuvent s’effec tuer en temps constant,
la complexité glo bale des opé ra tions néces saires à un par cours est O1 n 1 m 2 . Nous
allons voir comment, en uti li sant une file, il est pos sible de réa li ser cet objec tif.
82
che min de s à x existe dans l’arbo res cence rela tive au par cours seule ment si ce même
che min existe dans le graphe auquel l’algo rithme est appli qué ; d’autre part, s étant le
pre mier som met ouvert, il est aisé de véri fier que quelle que soit la manière dont le
par cours est réa lisé, tout som met des cen dant de s dans le graphe par couru est néces -
sai re ment un som met de l’arbo res cence ayant le som met s pour racine.
Dans ce cha pitre, nous avons donné dif fé rents algo rithmes per met tant de cal -
cu ler la fer me ture tran si tive d’un graphe. L’algo rithme le plus effi cace que nous
avions pré senté jus qu’alors était celui dû à Roy et Warshall de complexité O(n
3
).
L’algo rithme que nous venons de pré sen ter nous per met aussi d’obte nir la fer me ture
tran si tive d’un graphe. Il suf fit pour cela d’appli quer n fois cet algo rithme à par tir
de cha cun des n som mets du graphe. Comme nous le ver rons juste en des sous, il est
pos sible d’effec tuer le par cours d’un graphe avec une complexité O(n 1 m). Lorsque
le graphe consi déré comporte de nom breux arcs, c’est- à-dire m 5 O(n
2
), la complexité de ces par cours est O(n
2
), donc en effec tuant n par cours (un depuis chacun
des sommets) nous obte nons la fer me ture tran si tive d’un graphe avec la complexité
O(n
3
), ce qui est iden tique à la complexité de l’algo rithme de Roy- Warshall. En
revanche, si le graphe consi déré comporte peu d’arcs, c’est- à-dire m 5 O(n), ce qui
est le cas des graphes pla naires fré quem ment ren contrés en recherche opé ra tion nelle,
la complexité d’un par cours est alors O(m) 5 O(n). En effec tuant n par cours, nous
obte nons la fer me ture tran si tive d’un graphe avec une complexité O(n
2
). Pour ce
type de graphes, l’algo rithme effec tuant n par cours est alors plus effi cace que ceux
pré sen tés au début de ce cha pitre.
Tarjan a donné un algo rithme per met tant de résoudre le pro blème de l’acces si bi -
lité, de complexité O(m 1 n), utilisant un seul parcours du graphe.
3.2.3 Par cours en lar geur
Nous défi nis sons dans cette sec tion une stra té gie par ti cu lière de par cours de graphe
appe lée par cours en lar geur. Ce type de par cours est défini dans ce para graphe pour
les graphes orien tés, l’adap ta tion immé diate des algo rithmes, pro po sés ici, aux graphes non orien tés est lais sée au lec teur. Nous ver rons comment en uti li sant une file
comme struc ture de don nées, la complexité d’un algo rithme de par cours en lar geur
est O1 n 1 m 2 (nous rap pe lons plus bas en quoi consiste une file). Nous illus tre rons
ensuite l’effi ca cité des par cours en lar geur en mon trant comment déter mi ner les plus
courts che mins d’un graphe depuis un sommet s donné.
La stra té gie pour effec tuer un par cours en lar geur obéit aux deux règles sui -
vantes : tous les suc ces seurs non mar qués du som met en cours de visite sont
ouverts suc ces si ve ment et leurs numé ros d’ordre de prévisite seront donc consé cu -
tifs ; le som met visité à toute étape est, parmi les som mets ouverts, celui qui a été
ouvert le pre mier.
Comme nous l’avons mon tré un peu plus haut, si les opé ra tions per met tant de mettre
en œuvre une stra té gie par ti cu lière de par cours peuvent s’effec tuer en temps constant,
la complexité glo bale des opé ra tions néces saires à un par cours est O1 n 1 m 2 . Nous
allons voir comment, en uti li sant une file, il est pos sible de réa li ser cet objec tif.