Maintenant que nous avons étudié les notions les plus basiques, il est temps de passer à quelque chose de plus concret ! Dans ce cours, nous présentons deux manières simples d’effectuer un parcours dans un graphe (c’est à dire de se promener d’un sommet à l’autre). Pour cela, nous introduisons trois nouvelles structures de données : les files et les piles, qui vous serviront à implémenter ces parcours; et les arbres qui serviront à vous rendre compte de ce qui se passe vraiment lors d’un parcours.
Important ! L’implémentation de ces parcours peut être faite de plusieurs manières. L’une d’entre elles est particulièrement simple, mais nécessite de bien comprendre la notion de récursivité en programmation.
Pour la prochaine fois
Lors du troisième cours, nous vous demanderons de présenter votre solution pour ramasser un unique morceau de fromage dans le labyrinthe (“–pieces 1″). Vous pouvez nous expliquer comment vous le faites dans des labyrinthes sans boue (“–mud_density 0″).
N’oubliez pas que vous devrez présenter et justifier vos choix. Vous pouvez/devez vous appuyer sur des courbes illustrant vos propos.
Articles à étudier
- La complexité des algorithmes
- Les files et les piles
- Les arbres
- La récursivité dans les algorithmes
- Parcourir un graphe en profondeur
- Parcourir un graphe en largeur
Pour ceux qui souhaitent approfondir les notions, vous pouvez visiter aussi la page suivante :