10.2. Szélességi keresés

Több algoritmus alapja a szélességi keresés. Itt egy sor segítségével fedezi fel a program a gráfot, és épít fel ez alapján egy fát. Kezdetben a kezdőpontot, s-t szürkére színezi, majd a szürke csúcsok mindegyikének megkeresi a még fehér szomszédjait. Ezeket szürkére színezi, s felveszi egy sorba. Miután a szürke csúcs minden szomszédját meghatároztuk, feketére festjük. Lássuk a program futását a 10.2.1. ábrán látható gráfon. A kezdőcsúcs távolsága 0, minden más csúcs távolsága végtelen. Mivel a fehér oldalra fehér betűket nem érdemes írni, a következő színeket alkalmazzuk az soron következő ábrákon: fehér-zöld, szürke-kék, fekete-piros.

10.4. ábra - 10.2.1. ábra. Eredeti gráf

10.2.1. ábra. Eredeti gráf

10.5. ábra - 10.2.2. ábra. Kiinduló állapot, az a csúcsból kezdünk

10.2.2. ábra. Kiinduló állapot, az a csúcsból kezdünk

10.6. ábra - 10.2.3. ábra. Az a három szomszédja

10.2.3. ábra. Az a három szomszédja

10.7. ábra - 10.2.4. ábra. A d-nek nincs új szomszédja

10.2.4. ábra. A d-nek nincs új szomszédja

10.8. ábra - 10.2.5. ábra. Az f-nek viszont van, az e

10.2.5. ábra. Az f-nek viszont van, az e

10.9. ábra - 10.2.6. ábra. A g-nek sincs új szomszédja

10.2.6. ábra. A g-nek sincs új szomszédja

10.10. ábra - 10.2.7. ábra. Az e új szomszédjai a b és a h

10.2.7. ábra. Az e új szomszédjai a b és a h

10.11. ábra - 10.2.8. ábra. A b-nek nincs új szomszédja

10.2.8. ábra. A b-nek nincs új szomszédja

10.12. ábra - 10.2.9. ábra. A h-nak sincs, és ezzel a sor is kiürült

10.2.9. ábra. A h-nak sincs, és ezzel a sor is kiürült
Procedure SZÉLESSÉGI-KERESÉS(G,s) 
Input: G gráf 
Eredmény: a gráf alapján egy fát generál 
1  forall the u ∊ V − {s} do 
2     u.szín = FEHÉR 
3     u.táv = ∾ 
4     u.apa = Nil 
5  endfall 
6  s.szín = SZÜRKE 
7  s.táv = 0 
8  s.apa = Nil 
9  SORBA(Q,s) 
10 while not ÜRES(Q) do 
11    u = Q.fej 
12    forall the v ∊ Adj(u) do 
13       if v.szín == FEHÉR then 
14          v.szín = SZÜRKE 
15          v.táv = u.táv + 1 
16          v.apa = u 
17          SORBA(Q,v) 
18        endif 
19     endfall 
20     SORBÓL(Q) 
21     u.szín = FEKETE 
22 endw