Discuter:Algorithme de parcours en largeur

Un article de Wikipédia, l'encyclopédie libre.

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é.

[modifier] l'algo

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)

[modifier] Traitement des donnees

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.

[modifier] Traitement des donnees (réponse)

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);
}