Algorithme DFS et BFS en php

DEV - 12/01
1. Configuration du problème (arborescence) Un arbre générique (non binaire) : class Node { public...

1. Configuration du problème (arborescence)

Un arbre générique (non binaire) :

class Node { public function __construct( public int $value, public array $children = [] ) {} }
Entrer en mode plein écran Quitter le mode plein écran

Visualisation de l'arborescence

10 ┌───────┼────────┬────────┐ 1 2 3 4 | | | ┌──┴──┐ 5 6 7 8 9
Entrer en mode plein écran Quitter le mode plein écran

2. BFS (recherche en largeur d'abord)

Ce que signifie BFS

BFS visite les nœuds niveau par niveau → D'abord la racine → Puis tous les enfants → Puis les petits-enfants

Structure des données clés :File d'attenteRègle : Premier entré → Premier sorti (FIFO)

Algorithme BFS (concept)

  1. Mettre le nœud racine dans la file d'attente
  2. Tant que la file d'attente n'est pas vide :
  • Supprimer le nœud avant
  • Traitez-le
  • Ajouter tous ses enfants à la file d'attente

Code BFS (votre exemple, expliqué)

$file d'attente = new SplQueue(); $queue->enqueue($root); while (!$queu...
[Courte citation de 8% de l'article original]