Корисник:Mikrosam Akademija 4/BFS

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

Алгоритам

Алгоритамот користи квота(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

Pseudocode

Input: A graph G and a root v of G

The algorithm uses a queue data structure to store intermediate results as it traverses the graph, as follows:

Enqueue the root node Dequeue a node and examine it If the element sought is found in this node, quit the search and return a result. Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered. If the queue is empty, every node on the graph has been examined – quit the search and return "not found". If the queue is not empty, repeat from Step 2.

Note: Using a stack instead of a queue would turn this algorithm into a depth-first search.

In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspect all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on. Compare it with the depth-first search.