Szélességi keresés (algoritmus)

A szélességi keresés (breadth-first search) egy olyan fabejárási algoritmus, amely a fában a gyökértől kiindulva minden csúcsot bejárja. Az algoritmus lényege, hogy a fában igyekszik először a gyökérhez közelebbi csúcsokat átvizsgálni, és csak azután folytatja a keresést a mélyebb csúcsokon.

Programozási nyelvekben a megvalósítás általában sorral lehetséges.

Szélességi fabejárási példa Object Pascal ban:

procedure BreadthFirst( Root: TNode; Stream: TStream );
var
   Q: TNodeQueue;
   Node: TNode;
   i: Integer;
begin
   Q := TNodeQueue.Create;
   Q.Push( Root );
   while not Q.Empty do begin
      Node := Q.Pop;
      Node.Write( Stream );
      for i := 0 to Node.ChildCount-1 do
         Q.Push( Node.Child(i) );
   end;
   Q.Free;
end;

Az algoritmus fenti formája kört tartalmazó gráfok esetén végtelen ciklusba kerül. A probléma orvosolható, ha az elemeket a sorba helyezéskor megjelöljük, és csak a jelöletlen elemeket engedjük a későbbiekben felvenni a sorba.