Les meilleures sources algorithmes
Les meilleures sources algorithmesConsultez toutes les sources
Nombre d'auteurs : 1, nombre de sources : 15, dernière mise à jour : 4 janvier 2007
Sommaire→Algorithmes sur les graphes
Entrée:
Sélectionnez
G : un graphe, a priori quelconque.
X : un sommet du graphe à partir du quel on fait le parcours.Sortie:
Sélectionnez
A priori rien.Pseudo-Code :
Sélectionnez
INIT( G : T_Graphe )
DEBUT
POUR tous les sommets x du graphe FAIRE
x.couleur <- Vert
FIN POUR
FIN
-- Parcours en profondeur à partir de X
DFS( G : T_Graphe ; X : T_Sommet )
DEBUT
X.couleur <- orange
-- On peut effectuer une action ici sur X.
POUR tous les sommets y adjacents à X FAIRE
SI y.couleur = vert ALORS
DFS( G , y )
FIN SI
FIN POUR
X.couleur <- rouge
FIN
-- Fonction Principale :
DFS( G : T_Graphe )
DEBUT
INIT(G)
POUR tous les sommets x du graphe FAIRE
SI x.couleur = vert ALORS
DFS( G , x )
FIN SI
FIN POUR
FINNote:
Sélectionnez
La couleur du sommet a la signification suivante :
-> vert : sommet non traité.
-> orange : sommet en cours de traitement, il reste encore des arêtes adjacentes à traiter.
-> rouge : sommet totalement traité.Complexité :
Sélectionnez
O(n+m) où n est le nombre de sommets et m le nombre d'arêtes du graphe.Créé le 17 décembre 2006 par Romuald Perrot