Algorithme de numérotation post ordre par parcours en profondeur

Bonjour je connais l'algorithme de parcours en profondeur mais je ne vois pas l'implémentation qui permet de numéroter mes sommets en post- ordre.

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 35 36 37

typedef int sommet; typedef struct chainon { sommet st; struct chainon * suivant ; } Couple; typedef Couple * liste;   typedef struct { liste a[n_max]; int n; }graphe;   void parcours_en_prof(graphe g) { int marquage marque[n_max]; sommet x; for (x=0 ; x<g.n ; x++) marque[x] =0; for(x=0 ; x < g.n ; x++) if(!marque[x]) rech_prof(g,marque,x); } void rech_prof(graphe g, marquage marque,sommet x) { liste p; marque[x] = 1; p=g.a[x]; while(p != NULL) { if(!marque[p->st]) rech_prof(g,marque,p->st); p=p->suivant; } }

---

C'est bizarre, le post-ordre, on tend à voir ça plus pour des arbres que pour des graphes quelquonques...

Le graphe est-il sans cycle, au moins?

Graphe orienté sans arc réflexif , ce sont les données que j'ai !

Déjà, de quelles bases pars-tu? Possèdes-tu déjà des fonctions pour marquer en pré-ordre?

Non je n'en ai pas c'est vraiment la méthode qui me manque, ne l'ayant jamais vu de mes propres yeux !

En gros, tu dois maintenir quelque part un entier que tu incrémentes à chaque fois.
Comme ton code est récursif, tu dois passer à tes fonctions de parcours un pointeur vers cet entier.
Ou bien, un pointeur vers une structure contenant cet entier.

Exemple avec ton code:

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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

typedef int sommet; typedef struct chainon { sommet st; struct chainon * suivant ; } Couple; typedef Couple * liste;   typedef struct { liste a[n_max]; int n; }graphe;   /*structure contenant toutes les données du parcours*/ typedef struct { int flagsMarquage[n_max]; int numeros[n_max]; int numeroActuel; } Parcours;   void parcours_en_prof(graphe const *pcg) { Parcours prc; sommet x;   /* Initialisation */ for (x=0 ; x<pcg->n ; x++) { prc.flagsMarquage[x] =0; prc.numeros[x] =0; } prc.numeroActuel = 1;   for(x=0 ; x < pcg->n ; x++) { if(!prc.flagsMarquage[x]) rech_prof(pcg, &prc, x); } } void rech_prof(graphe const *pcg, Parcours *pPrc, sommet x) { Couple const *pc; pPrc->flagsMarquage[x] = 1; pc=pcg->a[x]; while(p != NULL) { if(!marque[pc->st]) rech_prof(pcg, pPrc, pc->st); pc=pc->suivant; } pPrc->numeros[x] = pPrc->numeroActuel; pPrc->numeroActuel++; }

---

Notes:

1. Vu que ton graphe est une liste de couples plutôt qu'un tableau de nœuds ayant chacun une liste de fils, on je peut pas mettre les numéros dans les nœuds eux-même (vu qu'on n'a pas de structure nœud) : J'ai donc mis les numéros dans la structure Parcours.
2. Je n'ai pas testé le code, je n'ai même pas essayé de le compiler.

Merci ;)

Note au passage qu'au lieu d'un tableau de listes chaînées, j'aurais plutôt fait des vrais sommets:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

typedef int NSommet;   typedef struct s_chainonArcSortant { NSommet numSommetDest; struct s_chainonArcSortant pSuiv; } ChainonArcSortant;   typedef struct s_sommet { char nom[nom_max]; ChainonArcSortant *pPremierArcSortant; } Sommet;   typedef struct s_graphe { Sommet sommets[n_max]; size_t nSommets; } Graphe;

---

Note que j'ai laissé le numéro en dehors de ça, car je me suis rendu compte que c'était une bonne idée après tout: Cela permet de créer plusieurs parcours différents du même graphe.

J'ai une question concernant ton code de recherche en profondeur :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

void rech_prof(graphe const *pcg, Parcours *pPrc, sommet x) { Couple const *pc; pPrc->flagsMarquage[x] = 1; pc=pcg->a[x]; while(p != NULL) { if(!marque[pc->st]) rech_prof(pcg, pPrc, pc->st); pc=pc->suivant; } pPrc->numeros[x] = pPrc->numeroActuel; pPrc->numeroActuel++; }

---

A la suite du while tu numérotes x,mais les autres sommets(qui sont successeurs de x) devraient être numérotés avant car c'est du post ordre.Non?

Oui, c'est ça: Ils sont numérotés dans leur propre appel à rech_prof().
Donc si on met l'affectation après le while, on a du post-ordre. Si on la met avant, on a du pré-ordre.