Шта је БФС?
Претрага у ширину (БФС) је заснована на преласку преко чворова додавањем суседа сваког чвора у ред преласка почевши од основног чвора. БФС за граф је сличан оном за стабло, са изузетком што графови могу имати циклусе. За разлику од претраге по дубини, сви суседни чворови на датој дубини се истражују пре него што се пређе на следећи ниво.
БФС алгоритам
Следећи кораци су укључени у коришћење претраге у ширину за истраживање графикона:
- Узмите податке за матрицу суседности графа или листу суседности.
- Направите ред и попуните га ставкама.
- Активирајте коријенски чвор (што значи да ћете добити коријенски чвор на почетку реда).
- Одложите главу реда (или почетни елемент), а затим ставите у ред све оближње чворове реда с лева на десно. Једноставно искључите главу и наставите са операцијом ако чвор нема оближње чворове које треба истражити. (Напомена: Ако се појави сусед који је претходно истражен или је у реду, немојте га стављати у ред; уместо тога, прескочите га.)
- Наставите на овај начин док се ред не испразни.
БФС Апплицатионс
Због флексибилности алгоритма, претрага у ширину је веома корисна у стварном свету. Ово су неки од њих:
- У пеер-то-пеер мрежи, равноправни чворови се откривају. Већина торрент клијената, као што су БитТоррент, уТоррент и кБитторент, користе овај процес за проналажење „семена“ и „вршњака“ у мрежи.
- Индекс је направљен коришћењем техника преласка графова у индексирању веба. Процедура почиње са изворном страницом као основним чвором и наставља свој пут до свих секундарних страница које су повезане са изворном страницом (и овај процес се наставља). Због смањене дубине рекурзивног стабла, претрага у ширину овде има инхерентну предност.
- Коришћењем ГПС навигационих система који користе ГПС, извршите претрагу у ширину да бисте лоцирали оближње локације.
- Чејнијева техника, која користи концепт претраге у ширину, користи се за сакупљање смећа.
Пример БФС Траверсал
За почетак, погледајмо једноставан пример. Почећемо са 0 као основним чвором и идемо низ график.
Корак 1: у реду(0)
Куеуе
| 0 |
Корак 2: Декуеуе(0), Енкуеуе(1), Енкуеуе(3), Енкуеуе(4)
Куеуе
| 1 | 3 | 4 |
Корак 3: Декуеуе(1), Енкуеуе(2)
Куеуе
| 3 | 4 | 2 |
4. корак: Декуеуе(3), Енкуеуе(5). Нећемо поново додати 1 у ред јер је 0 већ истражено.
Куеуе
| 4 | 2 | 5 |
5. корак: Декуеуе(4)
Куеуе
| 2 | 5 |
Корак 6: Декуеуе(2)
Куеуе
| 5 |
7. корак: Декуеуе(5)
Куеуе
Ред је сада празан тако да ћемо зауставити процес.
Јава програм за прво претраживање у ширину
Постоји неколико приступа поступања са кодом. Углавном ћемо разговарати о корацима који су укључени у имплементацију претраге у ширину у Јави. Листа суседности или матрица суседности се могу користити за чување графикона; било који метод је прихватљив. Листа суседности ће се користити за представљање нашег графа у нашем коду. Када имплементирате алгоритам за претрагу у ширину у Јави, много је лакше носити се са листом суседности јер морамо само да прођемо кроз листу чворова који су прикачени за сваки чвор када се чвор искључи из реда (или почетка) куеуе.
Графикон који се користи за демонстрацију кода биће идентичан оном коришћеном у претходном примеру.
БФСТраверсал.јава
import java.io.*; import java.util.*; public class BFSTraversal { private int node; /* total number number of nodes in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { node = v; adj = new LinkedList[node]; for (int i=0; i<v; i++) { adj[i]="new" linkedlist(); } que="new" void insertedge(int v,int w) adj[v].add(w); * adding an edge to the adjacency list (edges are bidirectional in this example) bfs(int n) boolean nodes[]="new" boolean[node]; initialize array for holding data int a="0;" nodes[n]="true;" que.add(n); root node is added top of queue while (que.size() !="0)" n="que.poll();" remove element system.out.print(n+' '); print (int i="0;" < adj[n].size(); iterate through linked and push all neighbors into if (!nodes[a]) only insert nodes they have not been explored already nodes[a]="true;" que.add(a); public static main(string args[]) bfstraversal graph="new" bfstraversal(6); graph.insertedge(0, 1); 3); 4); graph.insertedge(4, 5); graph.insertedge(3, graph.insertedge(1, 2); 0); graph.insertedge(2, graph.insertedge(5, system.out.println('breadth first traversal is:'); graph.bfs(0); pre> <p> <strong>Output:</strong> </p> <pre> Breadth First Traversal for the graph is: 0 1 3 4 2 5 </pre> <hr></v;>