Parcours de graphe

[sum87]

bonjour, je doit faire un programme en C++ sur les graphes et je sais pas comment faire des parcours en largeur et en profondeur.Est ce que quelqu'un peut m'aider?

[Patastronch]

T'as cherché au moins ? parceque la ca fait un peu "s'il vous plait donnez moi tout cru la solution en attendant je vais me faire un café merci". Tape parcours en largeur sur google t'auras ton bonheur, pareil pour le parcours en longueur. Sinon tu peux meme prendre ton cours.

[Dominique Lefebvre]

Ouai, relis ton cours d'algo, parce que c'est le b.a ba du cours d'algo sur les graphes...

[sum87]

Mon prof est incompétent, il nous interroge sur des trucs qu'on pas toujours vue, son cours est incompréhensible et mon prof te TD ne vaut pas mieux.
J'ai déjà cherché sur google et j'ai trouver des trucs mais c'est pas trés clair.

[ghghgh]

en gros un parcours en profondeur c'est :

parcours(noeudCourant)
llll si noeudCourant n'est pas valide
llll llll Retourner

llll pour tout voisin de noeudCourant
llll llll si voisin n'est pas marque
llll llll llll marque voisin
llll llll llll parcours(noeudVoisin)

voilà pour ce qui est du parcours en prof, pour chaque noeud, tu le marques, et tu rappelles sur tout les voisins, (tu peux le faire en récursif, comme ce que j'ai écris, ou tu peux le gérer avec une pile lifo qui contient les sommets à explorer, tu dépiles un sommet, et tu empiles les voisins non encore explorés)

pour le parcours en largeur :

soit F, une file fifo


parcours()
llll F = vide
llll F.ajouter(noeudDepart)
llll tant que file n'est pas vide
llll llll noeudCourant = F.debut()
llll llll marquer noeudCourant
llll llll pour tout voisin de noeudCourant
llll llll llll si voisin n'est pas marqué
llll llll llll llll F.ajouter(voisin)

et voilà, c'est pas bien compliqué, tu as
1. du papier et des crayons pour t'aider
2. google, notamment wikipedia

après pour l'implémentation en C++, ça dépend sur quel "noeud/objet" tu vas travailler, ce qui va te rendre la tâche plus ou moins difficile, mais si tu utilises les structures de la STL,
#include #include stack maPile; queue maFile;
tu ne devrais pas avoir trop de problèmes :)

bon courage