Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
253 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Parcours en profondeur et intervalle

Envoyé par bbsebb 
Parcours en profondeur et intervalle
il y a six semaines
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 six semaines et a été effectuée par AD.
Re: Parcours en profondeur et intervalle
il y a six semaines
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.
Re: Parcours en profondeur et intervalle
il y a six semaines
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 six semaines et a été effectuée par bbsebb.
Re: Parcours en profondeur et intervalle
il y a six semaines
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.
Re: Parcours en profondeur et intervalle
il y a six semaines
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 ...
Re: Parcours en profondeur et intervalle
il y a six semaines
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.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 148 605, Messages: 1 497 701, Utilisateurs: 28 280.
Notre dernier utilisateur inscrit Section Paloise.


Ce forum
Discussions: 886, Messages: 7 497.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page