Discussion :

[guipe]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Médinoc]

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?

[guipe]

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

[Médinoc]

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

[guipe]

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

[Médinoc]

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 C :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[guipe]

Merci

[Médinoc]

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

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[guipe]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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?

[Médinoc]

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.