Les meilleures sources algorithmesConsultez toutes les sources

Nombre d'auteurs : 1, nombre de sources : 15, dernière mise à jour : 4 janvier 2007 

 
OuvrirSommaireAlgorithmes 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
FIN

Note:

 
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
  

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2006 Developpez Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.