Co to jest BFS?
Wyszukiwanie wszerz (BFS) opiera się na przechodzeniu przez węzły poprzez dodanie sąsiadów każdego węzła do kolejki przechodzenia, zaczynając od węzła głównego. BFS dla wykresu jest podobny do drzewa, z tym wyjątkiem, że wykresy mogą mieć cykle. W przeciwieństwie do wyszukiwania w głąb, wszystkie sąsiednie węzły na danej głębokości są badane przed przejściem do następnego poziomu.
Algorytm BFS
Poniżej przedstawiono kroki związane z zastosowaniem przeszukiwania wszerz do eksploracji wykresu:
- Weź dane do macierzy sąsiedztwa lub listy sąsiedztwa grafu.
- Utwórz kolejkę i wypełnij ją przedmiotami.
- Aktywuj węzeł główny (co oznacza, że uzyskasz węzeł główny na początku kolejki).
- Usuń z kolejki nagłówek kolejki (lub element początkowy), a następnie umieść w kolejce wszystkie pobliskie węzły kolejki od lewej do prawej. Po prostu usuń z kolejki nagłówek i wznów operację, jeśli węzeł nie ma w pobliżu węzłów, które należy zbadać. (Uwaga: Jeśli pojawi się sąsiad, który był wcześniej badany lub znajduje się w kolejce, nie umieszczaj go w kolejce; zamiast tego pomiń go.)
- Kontynuuj w ten sposób, aż kolejka będzie pusta.
Aplikacje BFS
Ze względu na elastyczność algorytmu, wyszukiwanie wszerz jest całkiem przydatne w świecie rzeczywistym. Oto niektóre z nich:
- W sieci peer-to-peer wykrywane są węzły równorzędne. Większość klientów torrent, takich jak BitTorrent, uTorrent i qBittorent, wykorzystuje ten proces do wyszukiwania „nasion” i „równików” w sieci.
- Indeks jest tworzony przy użyciu technik przeglądania wykresów podczas przeszukiwania sieci. Procedura rozpoczyna się od strony źródłowej jako węzła głównego i przebiega w dół do wszystkich stron podrzędnych połączonych ze stroną źródłową (proces ten jest kontynuowany). Ze względu na zmniejszoną głębokość drzewa rekurencji, przeszukiwanie wszerz ma tutaj nieodłączną zaletę.
- Korzystanie z systemów nawigacji GPS wykorzystujących GPS, przeprowadza przeszukiwanie wszerz, aby zlokalizować pobliskie miejsca.
- Do zbierania śmieci wykorzystywana jest technika Cheneya, która wykorzystuje koncepcję przeszukiwania wszerz.
Przykładowe przejście BFS
Na początek spójrzmy na prosty przykład. Zaczniemy od 0 jako węzła głównego i będziemy podążać w dół wykresu.
Krok 1: Kolejkuj(0)
Kolejka
listonosz
| 0 |
Krok 2: Usuń z kolejki (0), Kolejkuj (1), Kolejkuj (3), Kolejkuj (4)
Kolejka
| 1 | 3 | 4 |
Krok 3: Usuń z kolejki(1), Kolejkuj(2)
Kolejka
| 3 | 4 | 2 |
Krok 4: Usuń z kolejki(3), Kolejkuj(5). Nie dodamy ponownie 1 do kolejki, ponieważ 0 zostało już zbadane.
Kolejka
| 4 | 2 | 5 |
Krok 5: Usuń z kolejki(4)
Kolejka
| 2 | 5 |
Krok 6: Usuń z kolejki(2)
Kolejka
| 5 |
Krok 7: Usuń z kolejki(5)
Kolejka
Kolejka jest teraz pusta, więc zatrzymamy proces.
Program Java do wyszukiwania wszerz
Istnieje kilka sposobów radzenia sobie z kodem. Będziemy głównie omawiać kroki związane z implementacją przeszukiwania wszerz w Javie. Do przechowywania wykresów można używać listy sąsiedztwa lub macierzy sąsiedztwa; każda metoda jest akceptowalna. Lista sąsiedztwa zostanie użyta do przedstawienia naszego wykresu w naszym kodzie. Implementując algorytm wyszukiwania wszerz w Javie, znacznie łatwiej jest poradzić sobie z listą sąsiedztwa, ponieważ musimy przeglądać listę węzłów dołączonych do każdego węzła dopiero wtedy, gdy węzeł zostanie usunięty z kolejki na początku (lub początku) kolejka.
Wykres użyty do zademonstrowania kodu będzie identyczny jak ten użyty w poprzednim przykładzie.
BFSTraversal.java
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;>