Forum d'entraide PHPFrance

Bonsoir,
Je suis en train de faire un code et j'ai besoin d'avoir un algorithme de recherche en largeur dans des graphes. J'ai essayé d'en fabriquer un, mais il ne ressemble pas à grand chose.

			$file = array($tableau[$c][0]); //$tableau[$c][0] est le point de départ de ma recherche en profondeur
			$arbre = array($tableau[$c][0]);	//$arbre correspond à l'ensemble des points se trouvant dans mon arbre de recherche en profondeur
			while(!empty($file)){
				$sommetFile = array_shift($file);
				//echo $sommetFile;
				if(!is_null($sommetFile)) {
					$voisin=array();
					
					
					//ici, il faut que je cherche tous les voisins de sommetFile et que je les mette dans le tableau $voisin
					
					
					foreach($resolution as $sommetFile) {
						
						}
					}
					
					
					foreach($resolution as $voisin){
						if(!in_array($voisin, $arbre)) {
							array_push($arbre, $voisin);
							array_push($file, $voisin);
						}              
					}
				}

Quelques explications sur le code: $tableau[$c][0] représente le point de départ de ma recherche en largeur. Tous les autre arcs de l'arbre sont stockés dans $resolution[/*sommet de départ*/][/*sommet de destination*/].
Je ne sais pas du tout si j'ai été claire; peut être faut-il que je montre l'intégralité de mon code, je ne sais pas...
Si quelqu'un peut m'aider, ça me rendrais vraiment service.

Merci, mais j'avais déjà troivé le pseudo-code Mais en fait je n'arrive pas à le programmer en php. Mon problème est surtout que je n'arrive pas à trouver les voisins de mes points je pense.

Comment est stocké ton graphe?

Voici un exemple de tableau qui contient mon graphe:

Édit: ce tableau s'appelle $resolution

Array
(
     [0] => Array ( [0] => 0 [1] => 1 [2] => 2 )
     [1] => Array ( [0] => 1 [1] => 1 [2] => 2 )
     [2] => Array ( [0] => 2 [1] => 1 [2] => 2 ) 
)

Ce tableau représente les arcs de mon graphe. En gros, ça fait Array( [0] => numéro du sommet de départ de l'arc [1] => numéro du sommet d'arrivé de l'arc [2] => valeur de l'arc )
Mon objectif, par une recherche en largeur, est de déterminer et de stocker dans un tableau $arbre tous les sommets qui sont dans le même arbre que mon sommet d'origine. Mon sommet d'origine est stocké dans un autre tableau et se note $tableau[$c][0]

Bonsoir tout le monde,
Je bloque toujours sur mon code. Je vous donne ma situation actuelle:
Dans le cadre d'un projet, j'essaie de programmer un algorithme de recherche en largeur dans un graphe, afin de déterminer tous les sommets d'un arbre. Mon arbre est déterminé par une série d'arcs, eux-même stockés dans un tableau $resolution de cette façon:

$resolution = array(
     [0] => Array ( [0] => 0 [1] => 1 [2] => 2 )
     [1] => Array ( [0] => 1 [1] => 1 [2] => 7 )
     [2] => Array ( [0] => 2 [1] => 1 [2] => 12 )
     [3] => Array ( [0] => 3 [1] => 0 [3] => 18 )
     // Array ( [0] => point de départ de l'arc [1] => point d'arrivé de l'arc [2] => valeur de l'arc, ce dernier point étant inutile pour une recherche en largeur )
)

Je cherche à mettre tous les points de cet arbre dans un tableau $arbre. Le point de départ de ma recherche en largeur se note $tableau[$c][0] .

J'ai trouvé sur wikipédia un pseudo-code de la recherche en largeur:
J'ai essayé de l'intégrer en PHP mais je n'y arrive pas, je n'arrête pas de m'emmêler les pinceaux. Pour l'instant, mon code ressemble à ça:

			array_push($file, $tableau[$c][0]); //$tableau[$c][0] est le point de départ de ma recherche en profondeur
					print_r ("<br><br><br>f==");
					print_r ($file);			
			array_push($arbre, $tableau[$c][0]);	//$arbre correspond à l'ensemble des points se trouvant dans mon arbre de recherche en profondeur
					print_r ("<br>ar==");
					print_r ($arbre);
			while(!empty($file)){
				$sommetFile = array_shift($file);
				//echo $sommetFile;
				if(!is_null($sommetFile)) {
					$voisin=array();
					
					
					$key = array_search($sommetFile, $resolution);
					print_r ("<br><br><br>sf==");
					print_r ($sommetFile);
					print_r ("<br><br><br>k==");
					print_r ($key);
					print_r ("<br><br><br>");

					
					
				foreach($resolution as $voisin){
					if(!in_array($voisin, $arbre)) {
						array_push($arbre, $voisin);
						array_push($file, $voisin);
					}              
				}

Pouvez vous m'aider?

Les voisins ne sont-ils pas frères,? donc ayant même père?

Salut

Un exemple des données sources et d'un résultat attendu pourraient simplifier la compréhension, car le code php n'est pas du tout parlant et l'algorithme ne semble pas correspondre aux données présentées.

$resolution = array(
     [0] => Array ( [0] => 0 [1] => 1 [2] => 2 )
     [1] => Array ( [0] => 1 [1] => 1 [2] => 7 )
     [2] => Array ( [0] => 2 [1] => 1 [2] => 12 )
     [3] => Array ( [0] => 3 [1] => 0 [3] => 18 )
     // Array ( [0] => point de départ de l'arc [1] => point d'arrivé de l'arc [2] => valeur de l'arc, ce dernier point étant inutile pour une recherche en largeur )
)

Code : Tout sélectionner

ParcoursLargeur(Sommet s): { f = CreerFile(); f.enfiler(s); marquer(s); TANT-QUE NON f.vide() FAIRE s = f.defiler(); afficher(s); POUR TOUT voisin de s FAIRE SI voisin non marqué FAIRE f.enfiler(voisin); marquer(voisin); FIN SI FIN POUR TOUT FIN TANT QUE }

En supposant que voisin est synonyme de "numéro du sommet d'arrivé de l'arc", alors une implémentation possible de l'algorithme adapté à tes données pourrait être.

<?php

$resolution = array(array(0, 1, 2), array(1, 1, 7), array(2, 1, 12), array(3, 1, 18));
$sommets = array();

$c = 2; // d'où vient $c ?
$f[] = $resolution[$c][0];
$marquer[$resolution[$c][0]] = true;
while(count($f)) {
  $s = array_shift($f);
  $sommets[] = $s; // pour afficher les sommets uniquement
  // extraires les voisins ([1] => numéro du sommet d'arrivé de l'arc?) PHP 5.3+
  $voisins = array_filter($resolution, function($tableau) use ($s) {return $tableau[0] == $s;});
  foreach($voisins as $voisin) { 
    if(!isset($marquer[$voisin[1]])) {
      $f[] = $voisin[1]; 
      $marquer[$voisin[1]] = true; 
    }
  }
}

var_dump($sommets);

?>

Si c'est dans la bonne direction et que la mémoire n'est pas un problème, alors une pré-indexation des "voisins" pourrait simplifier le code et accélérer l'exécution.

<?php

$resolution = array(array(0, 1, 2), array(1, 1, 7), array(2, 1, 12), array(3, 1, 18));
$sommets = array();
// pré-indexation des voisins ([1] => numéro du sommet d'arrivé de l'arc?)
$voisins = array();
foreach($resolution as $r) $voisins[$r[0]][] = $r[1];

$c = 2; // d'où vient $c ?
$f[] = $resolution[$c][0];
$marquer[$resolution[$c][0]] = true;
while(count($f)) {
  $s = array_shift($f); 
  $sommets[] = $s; // pour afficher les sommets uniquement
  foreach($voisins[$s] as $voisin) {
    if(!isset($marquer[$voisin])) {
      $f[] = $voisin; 
      $marquer[$voisin] = true;
    }
  }
}

var_dump($sommets);

?>

Bonne chance.