Chapitre 3 • Éléments de la théorie des graphes
86
rela tive au par cours est un plus court che min de s à x dans le graphe. Nous mon -
trons cette pro priété en effec tuant une récur rence sur la lon gueur du che min de s à x
dans l’arbo res cence. La pro priété est évi dem ment vraie pour le som met s : d(s) 5 0.
Supposons la éga le ment véri fiée pour tous les som mets situés à une dis tance d 2 1 de
s dans l’arbo res cence. Il résulte de cette hypo thèse que pour un som met x à la dis tance
d de s dans l’arbo res cence, un plus court che min de s à x dans le graphe est consti tué
d’au moins d arcs. Le che min de s à x dans l’arbo res cence est aussi un che min du graphe, il est consti tué de d arcs ; c’est donc un plus court che min de s à x dans le graphe.
Nous lais sons au lec teur le soin de véri fier que les valeurs d(x) cal cu lées par l’algo -
rithme cor res pondent effec ti ve ment au nombre d’arcs de ces che mins.
La complexité de cet algo rithme est évi dem ment iden tique à celle d’un par cours
en lar geur, c’est- à-dire O1 n 1 m2 en uti li sant une file.
Par cours en pro fon deur
Nous défi nis sons ici une autre stra té gie de par cours de graphe appe lée par cours en
pro fon deur. Dans cette par tie, nous déter mi nons ce type de par cours pour les graphes
non orien tés ; l’adap ta tion immé diate de l’algo rithme géné rique pro posé aux graphes
orien tés est lais sée au lec teur. Nous ver rons comment en uti li sant une struc ture de
don nées par ti cu lière appe lée pile (rap pe lée plus bas), il est pos sible d’obte nir une
complexité O1 n 1 m 2 pour un algo rithme effec tuant un par cours en pro fon deur.
La stra té gie uti li sée pour effec tuer un par cours en pro fon deur obéit à la règle sui -
vante : un som met qui était non mar qué n’est ouvert que s’il est adja cent au der nier
som met pré cé dem ment ouvert ; si un tel som met n’existe pas, le der nier som met
ouvert est alors fermé.
II est pos sible de déter mi ner le der nier som met ouvert en uti li sant une pile. Dans
ce cas, cette opé ra tion peut s’effec tuer en temps constant. La complexité obte nue
pour effec tuer le par cours en pro fon deur d’un graphe est alors O1 n 1 m2 .
Une pile est une liste ordon née d’élé ments pour laquelle seulement deux opé ra -
tions élé men taires peuvent s’effec tuer. La pre mière insère un élé ment au som met de
la pile ; la seconde opé ra tion sup prime l’élé ment situé au som met de la pile. On n’a
donc pas accès aux élé ments de la pile autres que celui situé au som met.
L’algo rithme géné rique effec tuant un par cours en pro fon deur d’un graphe non
orienté 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 et insé rer s au som met de la pile ;
3. tant que la pile n’est pas vide faire ;
4.
s’il existe un som met y non mar qué, adja cent au som met x situé au som met
de la pile ;
5.
alors ouvrir y et insé rer y dans la pile ;
6.
sinon fer mer le som met x et sup pri mer x de la pile.
On ren contre les syno nymes sui vants : « empi ler » pour « insé rer (en haut) dans
la pile » et « dépi ler » pour « sup pri mer (du haut) de la pile ».
86
rela tive au par cours est un plus court che min de s à x dans le graphe. Nous mon -
trons cette pro priété en effec tuant une récur rence sur la lon gueur du che min de s à x
dans l’arbo res cence. La pro priété est évi dem ment vraie pour le som met s : d(s) 5 0.
Supposons la éga le ment véri fiée pour tous les som mets situés à une dis tance d 2 1 de
s dans l’arbo res cence. Il résulte de cette hypo thèse que pour un som met x à la dis tance
d de s dans l’arbo res cence, un plus court che min de s à x dans le graphe est consti tué
d’au moins d arcs. Le che min de s à x dans l’arbo res cence est aussi un che min du graphe, il est consti tué de d arcs ; c’est donc un plus court che min de s à x dans le graphe.
Nous lais sons au lec teur le soin de véri fier que les valeurs d(x) cal cu lées par l’algo -
rithme cor res pondent effec ti ve ment au nombre d’arcs de ces che mins.
La complexité de cet algo rithme est évi dem ment iden tique à celle d’un par cours
en lar geur, c’est- à-dire O1 n 1 m2 en uti li sant une file.
Par cours en pro fon deur
Nous défi nis sons ici une autre stra té gie de par cours de graphe appe lée par cours en
pro fon deur. Dans cette par tie, nous déter mi nons ce type de par cours pour les graphes
non orien tés ; l’adap ta tion immé diate de l’algo rithme géné rique pro posé aux graphes
orien tés est lais sée au lec teur. Nous ver rons comment en uti li sant une struc ture de
don nées par ti cu lière appe lée pile (rap pe lée plus bas), il est pos sible d’obte nir une
complexité O1 n 1 m 2 pour un algo rithme effec tuant un par cours en pro fon deur.
La stra té gie uti li sée pour effec tuer un par cours en pro fon deur obéit à la règle sui -
vante : un som met qui était non mar qué n’est ouvert que s’il est adja cent au der nier
som met pré cé dem ment ouvert ; si un tel som met n’existe pas, le der nier som met
ouvert est alors fermé.
II est pos sible de déter mi ner le der nier som met ouvert en uti li sant une pile. Dans
ce cas, cette opé ra tion peut s’effec tuer en temps constant. La complexité obte nue
pour effec tuer le par cours en pro fon deur d’un graphe est alors O1 n 1 m2 .
Une pile est une liste ordon née d’élé ments pour laquelle seulement deux opé ra -
tions élé men taires peuvent s’effec tuer. La pre mière insère un élé ment au som met de
la pile ; la seconde opé ra tion sup prime l’élé ment situé au som met de la pile. On n’a
donc pas accès aux élé ments de la pile autres que celui situé au som met.
L’algo rithme géné rique effec tuant un par cours en pro fon deur d’un graphe non
orienté 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 et insé rer s au som met de la pile ;
3. tant que la pile n’est pas vide faire ;
4.
s’il existe un som met y non mar qué, adja cent au som met x situé au som met
de la pile ;
5.
alors ouvrir y et insé rer y dans la pile ;
6.
sinon fer mer le som met x et sup pri mer x de la pile.
On ren contre les syno nymes sui vants : « empi ler » pour « insé rer (en haut) dans
la pile » et « dépi ler » pour « sup pri mer (du haut) de la pile ».