BFS

Во теоријата на графови, breadth-first search (BFS) е стратегија за пребарување во граф кога пребарувањето е ограничено со две операции: (а) посетување и испитување на јазол во граф; (б) добивање пристап за посета на соседните јазли на моментално посетениот јазол. BFS започнува од коренот и ги испитува сите соседни јазли. Потоа за секој од тие јазли, ги посетува нивните соседни јазли кои не се откриени, и така натаму.

Како работи

ВFS e неинформиран начин на пребарување којшто се стреми да се прошири и да ги испита сите јазли од некој граф или комбинација на секвенци преку систематизирано пребарување низ секое решение. Со други зборови, исцрпно го пребарува цел граф или секвенца без оглед на некоја цел сè додека не ја пронајде.. Од гледна точка на алгоритмот, сите под-јазли добиени преку проширувањето на еден јазол се додадени на FIFO (First In, First Out) барање. Во типичната имплементација, јазлите којшто сè уште не се испитани за нивни соседни јазли се сместени во некој контејнер (како барање или поврзана листа) која што е наречена „отворена“ и веднаш од кога ќе се испита се става во контејнер наречен „затворен контејнер“.

Алгоритам

Алгоритамот користи квота(queue) податочна структура за да ги складира резултатите додека се движи низ графот:

1. Поставување на коренот во квотата 2. Отстранување на јазол од квотата

• Ако бараниот елемент е пронајден во јазолот, заврши го пребарувањето и врати резултат.
• Инаку поставиги сите наследници во квотата кои не се откриени.

3. Ако квотата е празна, тогаш секој јазол е посетен - завршиго пребарувањето и врати резултат „Не е пронајден“. 4. Ако квотата не е празна, повтори го вториот чекор.

Псевдокод

Влез : Граф G и корен v od G

1  procedure BFS(G,v):
2      create a queue Q
3      enqueue v onto Q
4      mark v
5      while Q is not empty:
6          t ← Q.dequeue()
7          if t is what we are looking for:
8              return t
9          for all edges e in G.incidentEdges(t) do
10             o ← G.opposite(t,e)
11             if o is not marked:
12                  mark o
13                  enqueue o onto Q

Особености

Комплексност на простор

Кога одреден број на темиња од графот се познати однапред и дополнителните структури на податоци се искористени за да се утврди кој темиња се веќе додадени во редот, комплексноста на простор може се прикажи како $O(|V|)$ каде што $|V|$ е кардиналност на множеството од темиња

Време на извршување

Времето на извршување може да се прикажи како $O(|E|+|V|)$ сè додека секое теме и секој раб ќе бидат истражени и во најлош случај. Забелешка: $O(|E|+|V|)$ може да варира помеѓу $O(|V|)$ и $O(|V|^{2})$, во зависност од познатите проценки на бројот на рабови во еден граф.

Примена

Breadth-first search може да се користи за да реши многу проблеми во теоријата на графови, на пример: Наоѓање на сите јазли во една поврзана компонента. Пронаоѓање на најкраток пат помеѓу два јазли u и v (мерна единица бројот на рабови) Серијализација/Десеријализација на бинарно дрво vs серијализација во подреден редослед, овозможувајќи ефикасно реконструирање на дрвото.

Пронаоѓање поврзани компоненти

Множеството на јазли постигнати од BFS (breadth-first search) ја формираат поврзаната компонента која го содржи почетниот јазол(коренот).

Тестирање бипартитност во граф

Бипартитното својство на еден граф ја означува неговата можност секое теме да биде обоено во една од две бои, така што не постојат две соседни темиња со иста боја. Користејќи BFS пребарување почнувајќи од секое теме, односно од едно теме во секоја компонента, и боејќи го секое следно соседно теме во обратна боја, може на лесен начин да се провери дали одреден град е бипартитен.

Наводи

• Knuth, Donald E. (1997), The Art Of Computer Programming Vol 1. 3rd ed., Boston: Addison-Wesley, ISBN 0-201-89683-4