1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| <?
$relations[] = "AAA|BBB";
$relations[] = "CCC|AAA";
$relations[] = "BBB|DDD";
$relations[] = "AAA|YYY";
$relations[] = "EEE|YYY";
$relations[] = "DDD|EEE";
// ici je parcours les relations pour établir une liste de connexion par ville
// vers les autres, c'est à dire, pour savoir facilement à quelles ville est
// reliée une ville. Par exemple $links['AAA'] contient la liste des villes
// accèssible depuis AAA
foreach($relations as $relation) {
list($ville1, $ville2) = explode('|', $relation);
$links[$ville1][] = $ville2;
$links[$ville2][] = $ville1;
}
print_r($links); // liste des relations
// cette fonction s'appelle recursivement, la tableau $links (expliqué
// plus haut) facilite les choses
// $paths est un tableau qui est complèté chaque fois qu'un chemin est
// trouvé. c'est le réultat.
function findPath($from, $to, $n, $stack=array()) {
global $paths, $links;
if(!$stack) $paths = array(); // init le tableau des résultats
$stack[] = $from;
// parcoure la liste des toutes les connexions depuis la ville $from
foreach($links[$from] as $ville) {
// $stack contient toutes les villes traitée dans un chemin possible,
// si la ville connectée à $from est la ville originale ($from du
// premier appel à fintPath), c'est qu'on tourne en rond, il faut sauter
// cette recherche.
if($ville==$stack[0]) continue; // boucle
// si la ville correspond à la destination finale c'est qu'on a trouvé un
// chemin possible, on places les villes parcourue ($stack) dans le
// tableau des chemins possibles.
if($ville==$to) $paths[] = array_merge($stack, $to);
// sinon, on rappel findPath pour qu'il cherche tous les chemin
// possible à partir d'une ville connectée à $from, soit $ville
// c'est un appel récursif, c'est ce qui est difficile à comprendre si
// on a pas l'habitute de la recursivité.
else if($n>0 && !in_array($ville, $stack)) findPath($ville, $to, $n-1, $stack);
}
}
$max_path = count($links);
// chemina de 'AAA' à 'DDD'
findPath('AAA', 'DDD', $max_path);
print_r($paths);
// chemina de 'CCC' à 'BBB'
findPath('CCC', 'BBB', $max_path);
print_r($paths);
?> |
Partager