Discussion:Algorithme de parcours en largeur

Autres discussions [liste]

Admissibilité
Neutralité
Droit d'auteur
Article de qualité
Bon article
Lumière sur
À faire
Archives
Commons

Cet article est indexé par le projet Mathématiques.

Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.

**Évaluation** de l’article « **Algorithme de parcours en largeur** »
Avancement	Importance	pour le projet
Bon début	Faible		Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues)

Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.

Vous êtes sûr ?[modifier le code]

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]

l'algo[modifier le code]

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 le code]

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 le code]

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 le code]

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 le code]

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 le code]

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]