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);
?> |
Recherche de chemins dans une table
Répondre avec citation
)
, je ne sais pas pourquoi j'ai utilisé de l'iteratif à la place du recursif 
, je voulais faire trop compliqué, ce n'était pas du tout comme sa que je voyais la solution ! 
Partager