Discussion:Algorithme de parcours en largeur

Dernier commentaire : il y a 25 jours par Simon l dans le sujet Complexité confusante
Autres discussions [liste]
  • Admissibilité
  • Neutralité
  • Droit d'auteur
  • Article de qualité
  • Bon article
  • Lumière sur
  • À faire
  • Archives
  • Commons

Vous êtes sûr ? modifier

Vous êtes sur que c'est correct cet algorithme? J'ai lu un algo dans un bouquin où on marquait avec trois couleurs!

Le principe du parcours en largeur est respecté.

Néanmoins l'implémentation avec trois couleurs pour un parcours en largeur ou profondeur est pédagogiquement plus parlant. Un sommet du graphe n'est plus marqué ou non marqué. Il est par exemple :

  • blanc pour non visité
  • gris si en cours de visite
  • noir si déjà visité

Selon le cas, il permettra de déceler les cycles, etc...


Il parcontre compléter l'article (ainsi que pour le parcours en profondeur) vis-à-vis de : L'algorithme de parcours en profondeur (ou DFS: Depth First Search) permet le parcours récursif d'un graphe quelconque. Car on ne visite ici le graphe qu'à partir d'un sommet et l'illustration ne montre pas que la visite d'un sommet n'effectue qu'une visite partielle du graphe. C'est d'autant plus vraie pour le cas générale d'un graphe orienté quelconque. Une autre critique est que l'exemple est peut-être trop... arborescent.

Pour le parcours d'un graphe il faut :

  • Démarquer tous les sommets du graphe
  • Faire une boucle for sur tous les noeuds du graphe, en lançant la visite d'un sommet si celui-ci n'a pas été visité (marqué) par la visite d'un noeud précédent. Une visite peut s'effectuer par l'algorithme présenté.


Votre référence est le Cormen et al. , non ? Personnellement, j'aime bien le Dasgupta et al.. Mieux, que vu et pas vu..., il stocke les distances à la source. Et si on présentait l'algo comme ça ? Mieux qu'un parcours en largeur, on a un algo qui calcule la distance à la source. --Fschwarzentruber (discuter) 11 octobre 2017 à 18:32 (CEST)Répondre
  Fschwarzentruber : En fait l'intervention date de 2005, j'ai juste mis un titre de section, pour que ce soit plus structuré. Pour ce qui est des changements sur l'article, fait comme tu l'entends :) . --Roll-Morton (discuter) 11 octobre 2017 à 23:34 (CEST)Répondre

Mais avec cet algo, on peut enfiler plusieurs fois le même sommet et ça sert à rien non?


Une précondition pour qu'un noeud puisse être visité et qu'il n'ait pas déjà été visité. Yorkgin 20 jun 2005 à 08:26 (CEST)

Traitement des donnees modifier

Quelqu'un peut-il rajouter les lignes de traitement dans le pseudo code? A savoir: Traitement infixe et Traitement suffixe. Idem pour le parcours en profondeur.

Je prefere ne pas le faire pour la simple raison que c'etait la raison de ma visite sur ces page :) C'est une information essentielle je pense.

Traitement des donnees (réponse) modifier

Il n'y a pas de notion de préfixe, infixe ou suffixe dans un parcours en largeur (parce que ça n'a pas de sens). Ca ne prend un sens que pour les algos récursifs (parcours en profondeur quoi). Pour rappel, dans le cas d'un arbre binaire:

typedef struct __Node Node;
struct __Node
{
	int id;
	Node * a;
	Node * b;
};


void prefix(Node * node)
{
	if (node == NULL)
		return;
	
	fprintf(stderr, "%d ", node->id);
	prefix(node->a);
	prefix(node->b);
}

void infix(Node * node)
{
	if (node == NULL)
		return;
	
	infix(node->a);
	fprintf(stderr, "%d ", node->id);
	infix(node->b);
}

void suffix(Node * node)
{
	if (node == NULL)
		return;
	
	suffix(node->a);
	suffix(node->b);
	fprintf(stderr, "%d ", node->id);
}

Implémentation modifier

Ne serait-ce pas pratique qu'il y ait une implémentation dans un langage quelconque pour avoir un exemple d'implémentation de cet algorithme ?--Agranger36 (d) 18 juillet 2009 à 14:16 (CEST)Répondre

Confusion parcours en profondeur modifier

La citation de Umberto Eco est un parcours en profondeur et non en largeur. — Le message qui précède, non signé, a été déposé par l'IP 77.109.122.83 (discuter), le 31 juillet 2020 à 02:19 (CEST)Répondre

Les explications sont peu claires mais il s'agit bien d'un parcours en profondeur. 92.188.154.209 (discuter) 8 janvier 2023 à 16:01 (CET)Répondre

Complexité confusante modifier

Dans le cadre de résumé de l'algorithme apparaissent des complexités en |V| et en |E|. Le reste de l'article ne mentionne pas qui est E (l'ensemble des arrêtes, pour Edges en anglais). Comme dans la plupart des articles approchant les maths, il faut être familier du sujet pour le comprendre et c'est un peu dommage.

Il y a aussi une complexité en O(b^d) qui sort de nulle part (en fait du bouquin de Russel et Norvig sur l'IA). Ces b et d sont balancés comme cela (mondialement, vu que les données sont importées sur toutes les pages mentionnant la BFS) sans aucun contexte. Un néophyte pourrait croire que l'algo est exponnentiel.

J'ignore comment procéder mais y a-t-il moyen d'harmoniser les notations dans les pages francophones (quitte à utiliser le |E| anglosaxon ?) ou de permettre une traduction du O(|V| + |E|) dans le cadre résumé ?

Plus généralement, il faudrait de toute façon avoir une note qui explique ce que sont V et E (ou A) soit de manière générale sur la page liée au graphes, soit juste à côté de la complexité. Simon l (discuter) 4 mai 2024 à 11:14 (CEST)Répondre

Revenir à la page « Algorithme de parcours en largeur ».