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.
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
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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.
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.
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 ?
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.
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 ?
En l'honneur de quoi ?
Si ton graphe est non orienté, tu pars du sommet que tu veux.
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 ...
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.
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.
Bravo. Tu sais copier-coller. Il ne reste plus qu'à donner du sens à tout ça.
Pour l'instant, tu ajoutes u à u.
Courage.