Parcours en profondeur et intervalle

Bonjour
Il y a qqch que je ne comprends pas. Si j'utilise l'algo de parcours en profondeur avec date de fin et de début, avec par exemple un graphe super simple : a -> b. Si je commence par b, j'aurai b : 1/2 et a: 3/4 alors que b devrait être inclus dans a ??

Dans tous les livres, on prend un sommet de départ qui correspond souvent à la racine, mais si je refais en partant de la fin, les intervalles ne fonctionnent pas. Ce n'est pourtant pas marqué de partir d'un sommet spécifique.

: function VISITE(G, u)
2: date <- date + 1 . u juste découvert
3: u.d <-date
4: u.couleur = gris
5: for tout v appartient Adj(u) do
6: if v.couleur = blanc then
7: v.pi <-u
8: VISITE(G, u)
9: end if
10: end for
11: u <-noir
12: date <-date + 1
13: u. f <-date
14: end function

Edité 2 fois. La dernière correction date de il y a sept semaines et a été effectuée par AD.

Bonjour

On n'aurait pas craint un contexte. Quel est le langage de programmation ? À quoi correspondent 1/2 et 3/4 ? (ne réponds pas "Les résultats en partant de b et a". Ça, on avait compris).

Quant au parcours en profondeur, tu as le droit de partir de "b". Mais tu n'exploreras que "b". Il n'y a aucune raison de remonter la flèche.
Par exemple, dans un arbre généalogique, un parcours en profondeur permettra de lister tous les descendants d'un individu. Mais si tu fais un parcours en profondeur à partir du dernier né, il n'a pas de descendance. La recherche s'arrête aussitôt.

Je vous reformule l'algo. Ce n'est pas un langage de programmation.

PP(G) :
POUR chaque sommet u de G
la couleur de u vaut blanc
FIN POUR
il n'y a aucun prédécesseur à u
la date; noté D, est à 0
POUR chaque sommet u appartenant à G
si la couleur de u est blanc
on applique la fonction visiter-PP(G,u)
FIN POUR

visiter-PP(G,u)
on incrémente la date, noté D, de 1
on met la date de début de u à date D
on met la couleur de u à gris
POUR chaque sommet v successeur de u
si v est de couleur blanche
on ajoute u au prédécesseur de v
on lance visiter-PP(G,v)
FIN POUR
on met la couleur de u à noir
on incrément la date D de 1
on met la date de fin de u à D.

1/2 et 3/4 correspond à la date de début et fin (datedebut/datefin)

Le but d'un parcours en profondeur, c'est de faire un graphe entier en général (comme dans cette algo). C'est une sous routine pour d'autre algo.

Si quelqu'un s'y connait un peu, merci de m'éclairer.



Edité 1 fois. La dernière correction date de il y a sept semaines et a été effectuée par bbsebb.

On n'a toujours pas de contexte. Il faut vraiment te tirer les vers du nez. Aide-nous à t'aider !

Ton graphe est-il orienté ou non orienté ? Que représente un sommet ? Que représente une arête ? Que viennent faire les dates au milieu ?

Citation
ssebss
Le but d'un parcours en profondeur, c'est de faire un graphe

Non. Faux. Comme son nom l'indique, le but du "parcours en profondeur" est de parcourir un graphe existant, de l'explorer. Pas de de le créer.

Citation
ssebss
POUR chaque sommet v successeur de u
(...)
on ajoute u au prédécesseur de v

Si v est le successeur de u, u est le prédécesseur de v. Tu vas donc systématiquement ajouter u à u. N'y a-t-il rien qui te choque ?

Citation
ssebss
b devrait être inclus dans a

En l'honneur de quoi ?

Citation
ssebss
Ce n'est pourtant pas marqué de partir d'un sommet spécifique.

Si ton graphe est non orienté, tu pars du sommet que tu veux.

Je vous recommande ce livre d'où est tiré mon exemple. Algorithmique de Cormen, leiserson, Stein.

Je ne vais pas réexpliquer ce qu'est un graphe, ni refaire ici toutes les démonstrations.

Si vous ne comprenez les deux algorithmes que je vous ai présenté, rien ne sert de répondre.

PS : si v est successeur de u, on peut ajouter u au prédécesseur de v ...

Je vois que tu as un handicap à la compréhension. Mais accroche-toi. Tu peux y arriver.

Citation
ssebss
Je vous recommande ce livre

Ce livre est suffisamment mauvais pour qu'il ne se suffise pas à lui-même.
De plus, je sais déjà. C'est toi qui a besoin d'explications.

Citation
ssebss
Je ne vais pas réexpliquer ce qu'est un graphe

Je ne veux pas ta théorie sur les graphes. Je veux que tu donnes la spécificité de ton graphe. Que symbolise un sommet dans ton graphe ? Pas un sommet dans l'absolu. Que symbolise une arête dans ton graphe ? Pas une arête dans l'absolu.

Citation
ssebss
PS : si v est successeur de u, on peut ajouter u au prédécesseur de v ...

Bravo. Tu sais copier-coller. Il ne reste plus qu'à donner du sens à tout ça.
Pour l'instant, tu ajoutes u à u.

Courage.

Liste des forums - Statistiques du forum

Total
Discussions: 148 744, Messages: 1 499 661, Utilisateurs: 28 309.
Notre dernier utilisateur inscrit erkl.

---

Ce forum
Discussions: 886, Messages: 7 507.