Représentation des graphes

Prototype


Version de

Parcours de graphes

Les algorithmes de parcours des arborescences s’adaptent aux graphes, en considérant que l’on parcourt chacune des arborescences associées aux sommets du graphe ; l’arborescence associée à un sommet est celle des descendants de ce sommet que l’on n’a pas encore visités.
Parcours en largeur

Rendered by QuickLaTeX.com

parcourir un graphe en largeur :
 visiter tous les sommets

visiter un sommet s :
 SI s n'a pas encore ete enfile
  ALORS enfiler s ;
   TANT QUE la file nest pas vide
     soit n le premier sommet de la file ;
     {traitement de n}
     defiler ;
     enfiler tous les successeurs
     non encore enfiles de n
    FIN TANT QUE
 FIN SI
Preuve du programme : chaque sommet est visité, donc enfilé au moins une fois ; or, on ne peut enfiler que des sommets non encore enfilés ; par conséquent, chaque sommet est enfilé exactement 1 fois. À chaque passage dans la boucle tant que, on défile un sommet différent, donc chaque procédure visiter se termine. À la sortie de visiter, la file est vide ; donc chaque sommet aura été défilé, et par conséquent traité, exactement 1 fois. Complexité : Chaque sommet est traité 1 fois, et chaque arc est examiné 1 fois (lors du traitement de son origine). La complexité est donc de l’ordre de max(\|A\|, \|S\|).
Parcours en profondeur (récursif)
\medskip
\centerline{{\sc Fig.} \thesubsection — {\it Ordre de visite : 1, 2, 4, 3, 5 ;}}
\centerline{\it de post-visite : 1, 5, 3, 4, 2}
\addcontentsline{lof}{section}{Ordre de visite et de post-visite}
\end{figurette}
parcourir un graphe en profondeur :
 visiter tous les sommets

visiter un sommet s :
 SI s n'a pas encore ete visite
 ALORS
  {pre-traitement de s}
  visiter tous les successeurs de s
   {post-traitement de s}
FIN SI
Preuve du programme : chaque sommet est visité exactement 1 fois. Complexité : chaque sommet est visité 1 fois, chaque arc d’origine est examiné 1 fois. La complexité est donc de l’ordre de max(\|A\|, \|S\|).
Représentation des graphes