algorithme récursif et itératif

Bonjour, je me pose une question par rapport à un graphe quelconque comportant n nœuds tel que n > 100000 (donc au max (n*(n-1))/2 arêtes).
Dans un tel cas, quel type d'algorithme est le plus adapté : le récursif ou l'itératif par exemple dans le parcours en profondeur ?

Personnellement je dirais l'itératif qui a moins de chance de saturer la pile d'exécution, mais là pareil transformer un algorithme récursif en itératif signifie simuler la pile créer par la récursivité par une structure de données de type pile, et je me demande si cette pile (la structure de données est plus performante que la pile d'exécution créer par la récursivité). En bref quoi privilégier ?

Citation:

---

Personnellement je dirais l'itératif qui a moins de chance de saturer la pile d'exécution

---

j'aurais dit que le récursif est mieux si tu ne fais que parcourir l'arbre, on peut, je pense, sans peine, libérer de la mémoire au fur et à mesure. non ? je n'en suis pas sûr ^^

le truc c'est que j'ai l'intention de modifier le parcours en profondeur pour lui permettre de détecter les cycles dans le graphe

il y a le DFS (depth first search), parcours en profondeur d'un graphe
[ame]http://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_profondeur[/ame]
(une boucle pour chaque fils et un appel récursif pour chacun...)

après sinon tu as le le BFS (Breadth First Search), le parcours en largeur !
il utilise une file de type FIFO (first in first out)
[ame]http://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_largeur[/ame]

Citation:

---

le truc c'est que j'ai l'intention de modifier le parcours en profondeur pour lui permettre de détecter les cycles dans le graphe

---

je te conseilles d'utiliser le DFS en le modifiant à ta sauce. cependant, compter les cycles en même temps... il y a une algo je crois : [ame]http://en.wikipedia.org/wiki/Cycle_detection[/ame] (il est très drôle tu vas voir). je ne pense pas que ce sera de la tarte pour coupler (si c'est possible) le DFS et le "tortoise and hare" :)

bonne chance en tout cas !

Citation:

---

quel type d'algorithme est le plus adapté : le récursif ou l'itératif ?

---

- Le récursif pour la facilité de programmation.
- La transformation en iteratif pour la performance et l'occupation mémoire.

Comme tu le penses, Un récursif (bien) transformé est en principe moins gourmand que le récursif.

Un algorithme itératif de parcours de graphe est finalement assez simple.

On se base en général sur 2 ensembles :
- 1 ensemble des éléments visité
- 1 ensemble des éléments à visiter

Je pense que tu imagines le reste :
- on initialise les visité à vide, les "à visiter" avec le sommet de départ
- Puis on boucle tant qu'il reste des éléments à visiter (en ajoutant évidemment chaque enfants du sommet courant dans l'ensemble des éléments à visiter). pis si le sommet courant est déjà visité, on saute l'étape

merci pour vos réponses
Donc si j'ai bien compris il me faudrait faire un algorithme itératif pour viser la rapidité d'exécution ?

L'algorithm des rangs permet de détécter assez simplement si oui ou non il existe des cycles. Normalement il ne retourne pas ces cycles ( il s'arrête au premier) mais tu devrais pouvoir en sortir quelque chose.