theorie des graphes/plus long chemin

Bonjour à tous,
    J'ai un tp à faire sur un labyrinthe apparemment "très classique" mais malgré ça j'ai beauuucoup de mal à le faire.
Mon problème n°1: J'ai méme pas compris cette question:

 Inonder le labyrinthe en parcourant tous les chemins du labyrinthe

mon probléme n°2: Je ne sais pas du tout comment on fait pour trouver le plus long chemin enfin je sais qu'il faut utiliser un

parcours DFS mais j'arrive pas à l'appliquer.

 Merci à tous ceux qui voudront m'aider.

Salut,

Pour innonder ton labyrinthe
il faut que tu fasses un parcours qui a partir de l'entrée de ton labyrinthe passe par toutes les cases atteignables de ton labirynthe.

Un parcours recursif est l'ideal tu parcours chaque chemin tant que tu n'es pas blqoué ou arrive à la fin.

Pour le chemin le plus long
tu retiens le chemin le plus long (0 à l'init)

et dés que tu arrives à la fin tu compares avec la valeur initiale si > alors tu changes la valeur stockée et sinon tu recommence
si tu es en cul de sac tu reprends le chemin suivant dans le parcours
l'algo d'innodation te permettta de parcourir tout le labyrinthe

il suffit de modifier le DFS pour compter le nombre de cases entre le debut et la fin de ton laby

Aide pour le DFS
http://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_profondeur

Merci pour la 1ere question j'ai enfin réussi à la faire.Mais pr ce qui est du plus court chemin u encore le plus long je tombe a chaque fois sur un résultat bizarre "DEUX CASES QUI NE SONT PAS VOISINES" ce qui est bien sur archi faux!!! Et je vois pas où est le probléme

Ton initilisation est-elle correcte?

Regardes avec un labyrinthe plus petit?
Trace les numeros de cases par ou tu passes si c'est possible

Mais je ne peux aider?

justement le avec lequel je travaille est déja petit.Je peux si tu veux bien te l' envoyer par mail et y jeter un coup d'oeil stp en plus c'est à rendre aprés demain et j'ai fait tt mon possible je déséspére
 et  Merci beauuuucoup

salut

envoie ton code ici, ca ira plus vite.


innonder son laby, ce n'est pas qqch de vraiment recursif : il s'agit d'un parcours en profondeur : ca se fait avec une file first in first out.

tu mets la case de depart dans la file.
tant qu'il y a une case dans la file, faire :
   si on avait pas deja parcourru cette case, faire :
      mettre dans la file les cases qui touchent la case courante.
   fin si
fin tant que

en faisant ca, nos goutes d'eau (qui parcourent en meme temps tout les chemins) vont toutes a la meme vitesse.

Travail à compléter

voici exactement en quoi ca consiste:
aidez moi s'il vous plait parce que je dois le rendre  demain et je m'en sors pas toute seule j'ai à peine fait la 1ere question!!!

 

Question 2.1

Soit le labyrinthe suivant extrait du fichier minizoo.laby :           +-+-+-+-+

|I  |   |

+-+ +-+-+

| |   | |

+ + + +-+

| | | | |

+-+ + +-+

|      O|

+-+-+-+-+

Représentez l' espace d'états de son graphe non orienté. En déduire toutes ses composantes connexes. Puis donnez la représentation mémoire de sa matrice port.

 

Question 2.2

En vous servant des classes fournies, définissez et implémentez en C++ une méthode dans la classe Chemins qui recherche et affiche toutes les composantes connexes du labyrinthe.

 

Question 2.3

On souhaite faire trois parcours de chemins d'un sommet de départ au sommet de sortie :

1-     Inonder le labyrinthe en parcourant tous les chemins du labyrinthe,

2-     Chercher le plus court chemin en parcourant le labyrinthe en largeur (BFS) avec une file d'attente : voir les méthodes enfiler et defiler de la classe ListeNoeuds.

3-     Chercher le plus long chemin en parcourant le labyrinthe en profondeur (DFS) avec une pile : voir la méthode empiler de la classe ListeNoeuds,

STOP

On n'est pas la pour faire les programmes en entier ;-)

Voila une source qui peut aider

http://www.cppfrance.com/codes/COMPOSENTE-CONNEXES-GRAPHE_47392.aspx

salut

on a pas pour habitude de faire les tps des gens a leur place.

si tu nous disait precisement sur quoi tu bloques, que tu nous montrait ton code, et l'erreur qui te pose probleme, on pourrait peut-etre t'aider, mais certainement pas te le faire a ta place.

oui je sais!!!!! Mais je demande juste des indications pas plus et en plus j'ai déja essayé de le faire!!!

Mon probléme c'est quand je fais la file et je combine les résultats de l'affichage je trouve un résultat IMPOSSIBLE à moins qu'il saute!!!ce qui n'est pas possible.
Donc si quelqu'un voit où est le probléme je lui serai reconnaissante!!

Merci pour ceux qui voudront bien m'aider.
Une débutante en programmation déséspérée.