- <?php
-
- function connected($start,$end,$order,$connections){
-
- $bool = 0;
- $resultag = 0;
- $link= 0;
- $j=0;
- $arbre[$link] = $start;
- $trace[$link] = $start;
- $newtrace[$link] = $start;
-
- while($bool==0){
-
- $next = count($newtrace);
- $link = count($arbre);
-
- for ($j=0;$j<$next;$j++){
-
- $i=0;
- foreach ($order as $key => $val) {
- if ($val != $newtrace[$j]) $i++;
- else break;
- }
-
- $temp_arbre = $arbre[$j];
- $max = count($connections[$i]);
-
- for ($k=0;$k<$max;$k++){
- $m = 0;
- if (!in_array($connections[$i][$k],$trace)){ // j'ajoute seulement les points inconnus
- $m++;
- $trace[] = $connections[$i][$k];
- $newtrace[] = $connections[$i][$k];
- $arbre[] = $temp_arbre.$connections[$i][$k];
-
- if ($connections[$i][$k] == $end){
- $result = $arbre[count($arbre)-1];
- $resultag++;
- $bool = 1;
- }
- }
- }
- }
- if ($m == 0)
- $bool = 1;
- }
-
- if ($resultag > 0){
- echo 'Le chemin entre '.$start.' et '.$end.' est le suivant: ';
-
- for ($i=0; $i<strlen($result)-1; $i++)
- echo $result[$i].' => ';
- echo $result[strlen($result)-1];
-
- }
- else echo 'Pas de liens entre '.$start.' et '.$end;
- }
-
- // connections
- //
- // Il s'agit d'un arbre non valué
-
- $connections = array();
- $order = array();
-
- $order = array('A','B','C','D','E','F','G');
- $connections[0][0] = 'B';$connections[0][1] = 'C'; // A
- $connections[1][0] = 'A';$connections[1][1] = 'C';$connections[1][2] = 'E'; // B
- $connections[2][0] = 'A';$connections[2][1] = 'B';$connections[2][2] = 'D';$connections[2][3] = 'E';$connections[2][4] = 'F'; // C
- $connections[3][0] = 'C';$connections[3][1] = 'F';$connections[3][2] = 'G'; // D
- $connections[4][0] = 'B';$connections[4][1] = 'C'; // E
- $connections[5][0] = 'B';$connections[5][1] = 'C';$connections[5][2] = 'D'; // F
- $connections[6][1] = 'D'; // G
-
- // Y a-t-il une connection dans l'arbre entre E et G?
-
- $start = 'E';
- $end = 'G';
-
- connected($start,$end,$order,$connections);
-
- ?>
<?php
function connected($start,$end,$order,$connections){
$bool = 0;
$resultag = 0;
$link= 0;
$j=0;
$arbre[$link] = $start;
$trace[$link] = $start;
$newtrace[$link] = $start;
while($bool==0){
$next = count($newtrace);
$link = count($arbre);
for ($j=0;$j<$next;$j++){
$i=0;
foreach ($order as $key => $val) {
if ($val != $newtrace[$j]) $i++;
else break;
}
$temp_arbre = $arbre[$j];
$max = count($connections[$i]);
for ($k=0;$k<$max;$k++){
$m = 0;
if (!in_array($connections[$i][$k],$trace)){ // j'ajoute seulement les points inconnus
$m++;
$trace[] = $connections[$i][$k];
$newtrace[] = $connections[$i][$k];
$arbre[] = $temp_arbre.$connections[$i][$k];
if ($connections[$i][$k] == $end){
$result = $arbre[count($arbre)-1];
$resultag++;
$bool = 1;
}
}
}
}
if ($m == 0)
$bool = 1;
}
if ($resultag > 0){
echo 'Le chemin entre '.$start.' et '.$end.' est le suivant: ';
for ($i=0; $i<strlen($result)-1; $i++)
echo $result[$i].' => ';
echo $result[strlen($result)-1];
}
else echo 'Pas de liens entre '.$start.' et '.$end;
}
// connections
//
// Il s'agit d'un arbre non valué
$connections = array();
$order = array();
$order = array('A','B','C','D','E','F','G');
$connections[0][0] = 'B';$connections[0][1] = 'C'; // A
$connections[1][0] = 'A';$connections[1][1] = 'C';$connections[1][2] = 'E'; // B
$connections[2][0] = 'A';$connections[2][1] = 'B';$connections[2][2] = 'D';$connections[2][3] = 'E';$connections[2][4] = 'F'; // C
$connections[3][0] = 'C';$connections[3][1] = 'F';$connections[3][2] = 'G'; // D
$connections[4][0] = 'B';$connections[4][1] = 'C'; // E
$connections[5][0] = 'B';$connections[5][1] = 'C';$connections[5][2] = 'D'; // F
$connections[6][1] = 'D'; // G
// Y a-t-il une connection dans l'arbre entre E et G?
$start = 'E';
$end = 'G';
connected($start,$end,$order,$connections);
?>