BFS

Од Википедија, слободната енциклопедија
Прејди на: содржини, барај
Breadth-first-tree.svg

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

Како работи[уреди]

Animated BFS.gif

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

Алгоритам[уреди]

GermanyBFS.svg

Алгоритамот користи квота(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) ја формираат поврзаната компонента која го содржи почетниот јазол(коренот).

Референци[уреди]

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