> Les arbres BSP ça permet d'utiliser les distances?
- oui, mais je reconnais que ça risque d'être un peu lourd pour ce qu'il veut faire
> graphe
- c'est la deuxième solution. Il y a deux parcours de base dans un graphe: en profondeur, et en largeur. Pour ces deux parcours, il te faut un booléen dans chaque sommet pour indiquer si le sommet a été traversé.
- parcours en largeur: d'abord mettre le booléen ``parcourru`` de tous les sommets à ``faux``. Ensuite on part d'un sommet, en l'occurence pour ce problème la ville à partir de laquelle s'effectue la recherche. C'est le sommet courant. Pour chaque sommet adjacent au sommet courant (chacune des villes les plus proches) qui n'a pas encore été parcourru, ajouter ce sommet à la liste des sommets parcourus et mettre le booléen ``parcourru`` à Vrai. Puis recommencer l'opération avec chaque nouveau sommet découvert précédemment. Pour ce problème, s'arrêter quand la distance devient trop grande, ou que le nombre de villes parcourrues atteint une limite. Trier le résultat.
- parcours en longueur: idem, sauf au lieu de parcourrir d'un coup tous les sommets adjacents, marquer la position en ajoutant le sommet dans une pile, aller au premier sommet adjacent, recommencer. Quand il n'y a plus de sommet adjacent non parcourrus pour le sommet courant, dépiler l'ancien sommet courant, recommencer. Quand la pile est vide, on a terminé.
Dans ce problème, il reste à construire le graphe, c'est à dire déterminer par avance quelles sont les villes adjacentes à chaque ville.