Parcours en profondeur et intervalle

bbsebb

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

PetitLutinMalicieux

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.

bbsebb

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.

PetitLutinMalicieux

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 ?

ssebss a écrit:

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.

ssebss a écrit:

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 ?

ssebss a écrit:

b devrait être inclus dans a

En l'honneur de quoi ?

ssebss a écrit:

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.

bbsebb

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 ...

PetitLutinMalicieux

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

ssebss a écrit:

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.

ssebss a écrit:

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.

ssebss a écrit:

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.

AlainLyon

Bonjour, je n'ai jamais entendu parler de la conjecture des trois couleurs ! Rappelons que pour un graphe planaire l'indice de coloration est $4$.