Parcours en profondeur ( bonne implémentation?)

Bonjour,
J'ai implémenté l'algorithme de parcours en profondeur récursivement en utilisant les piles , mais je voudrais savoir ce que vous pensez de mon implémentation car je ne suis pas sur d'avoir fait la meilleur méthode pour implémenter cet algo .

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void visiter(Graphe G,int sommet)
{
    if (G.nb_traites<G.n)
    {
        int i;
        printf("sommet explore ................: %d\n",sommet);
        G.tabSomm[sommet].marque=1;                                    //marquage du sommet explore
        for (i=0;i<G.n;i++)
        {
            if ((G.matrice[sommet][i]==1)&&(G.tabSomm[i].marque==0))   // Si on a trouve un voisin non marque..
            {
                G.nb_traites++;
                printf("Successeur trouve : %d\n",i);
                Empiler(&G,sommet);
                visiter(G,i);
            }
        }
        printf("Pas de Successeur trouve\n");
        Depiler(&G,&sommet);                                           //si tous les voisins sont marques on retourne au sommet pere
        visiter(G,sommet);
    }
    else
    {
        exit(0);                                                      //tous les sommets on ete explores : exit
    }
}

Citation:
Envoyé par Gottfried
Bonjour,
J'ai implémenté l'algorithme de parcours en profondeur récursivement en utilisant les piles , mais je voudrais savoir ce que vous pensez de mon implémentation car je ne suis pas sur d'avoir fait la meilleur méthode pour implémenter cet algo .
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 void visiter(Graphe G,int sommet) { if (G.nb_traites<G.n) { int i; printf("sommet explore ................: %d\n",sommet); G.tabSomm[sommet].marque=1; //marquage du sommet explore for (i=0;i<G.n;i++) { if ((G.matrice[sommet][i]==1)&&(G.tabSomm[i].marque==0)) // Si on a trouve un voisin non marque.. { G.nb_traites++; printf("Successeur trouve : %d\n",i); Empiler(&G,sommet); visiter(G,i); } } printf("Pas de Successeur trouve\n"); Depiler(&G,&sommet); //si tous les voisins sont marques on retourne au sommet pere visiter(G,sommet); } else { exit(0); //tous les sommets on ete explores : exit } }
On n'a pas trop de vision sur la fonction empiler() et la structure G donc on peut pas trop détailler mais à première vue, ça semble correct mis à part le exit car les conventions veulent qu'on ne sorte jamais d'un programme autrement que par le main(). Autrement dit, si une fonction appelle "Visiter()", alors il faut que cette fonction continue son code une fois l'appel à "Visiter()" terminé.

On peut optimiser l'écriture du code en inversant le test if () et en mettant un "continue" si le test inversé devient vrai ce qui évite une indentation mais ça n'optimise que l'affichage du source et non sa vitesse d'exécution.

Tout semble correct, à part la remarque faite par Sve@r : il ne faut jamais par convention (et par soucis de simplicité) utiliser exit dans une sous-routine.

Sinon une petit remarque d'implémentation : tu a tenté de cacher l'implémentation du graphe en utilisant un typedef, très bien, mais pourquoi ne pas être allé au bout ?

Je te conseille de rajouter dans le module où tu définit le graphe, les fonctions :
Code:

1 2 3 4 5 void marquer_sommet(Graphe g,int sommet,int marque); int get_nombre_visite(Graphe g); int get_nombre_traites(Graphe g); void incremente_nombre_traites(Graphe g);
ainsi qu'un itérateur sur les sommets adjacents d'un sommet.

voici les structures , j'ai vu sur plusieurs sites qu'il fallait implémenter l'algorithme avec les piles mais je ne suis pas sur que l'on puisses considérer que j'ai utiliser la structure de donnée LIFO(pile) dans mon implémentation puisque je n'ai pas vraiment de pile ?
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 typedef struct { int marque; }Sommet; typedef struct { int n; int nb_elem; int nb_traites; int *tab; int **matrice; Sommet *tabSomm; }Graphe; int Empiler(Graphe* pP,int elem) { if (pP->nb_elem>=pP->n) return 1; pP->tab[pP->nb_elem] = elem; pP->nb_elem++; return 0; } int Depiler(Graphe *pP,int *pelem) { if (pP->nb_elem==0) return 1; *pelem=pP->tab[pP->nb_elem-1]; pP->nb_elem--; return 0; }