Бортовой журнал Ктулху

Graphs in PHP in 5 Minutes (BFS)

A graph is a set of connected points — just like people in a social network, cities on a map, or links between web pages.

Sometimes we need to find the shortest connection — for example, the fewest hops between two people. That’s where Breadth-First Search (BFS) helps.

It explores all neighbors first, then moves level by level — guaranteeing the shortest path in an unweighted network.

1761468831104

Example in PHP:

$graph = [
'Anna' => ['Bob','Clara'],
'Bob' => ['Anna','Derek','Ella'],
'Clara' => ['Anna','Fred'],
'Derek' => ['Bob'],
'Ella' => ['Bob','Fred'],
'Fred' => ['Clara','Ella','Gina'],
'Gina' => ['Fred']
];
function shortestPath($graph,$start,$goal){
$q=new SplQueue(); $visited=[]; $chain=[]; $visited[$start]=1; $q->enqueue($start);
while(!$q->isEmpty()){
$v=$q->dequeue();
foreach($graph[$v]??[] as $n){
if(!isset($visited[$n])){
$visited[$n]=1; $chain[$n]=$v; $q->enqueue($n);
}
}
}
if(!isset($chain[$goal])) return [];
$r=[$goal]; while(end($r)!==$start) $r[]=$chain[end($r)];
return array_reverse($r);
}
var_dump(shortestPath($graph,'Anna','Gina'));

Result: we obtain the shortest path ['Anna','Clara','Fred','Gina'].

1761469364143