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:

1. Weź dane do macierzy sąsiedztwa lub listy sąsiedztwa grafu.
2. Utwórz kolejkę i wypełnij ją przedmiotami.
3. Aktywuj węzeł główny (co oznacza, że ​​uzyskasz węzeł główny na początku kolejki).
4. 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.)
5. 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:

1. 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.
2. 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ę.
3. Korzystanie z systemów nawigacji GPS wykorzystujących GPS, przeprowadza przeszukiwanie wszerz, aby zlokalizować pobliskie miejsca.
4. 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

Krok 2: Usuń z kolejki (0), Kolejkuj (1), Kolejkuj (3), Kolejkuj (4)

Kolejka

Krok 3: Usuń z kolejki(1), Kolejkuj(2)

Kolejka

Krok 4: Usuń z kolejki(3), Kolejkuj(5). Nie dodamy ponownie 1 do kolejki, ponieważ 0 zostało już zbadane.

Kolejka

Krok 5: Usuń z kolejki(4)

Kolejka

Krok 6: Usuń z kolejki(2)

Kolejka

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;>