Какво е BFS?
Търсенето първо в ширина (BFS) се основава на преминаване на възли чрез добавяне на съседите на всеки възел към опашката за преминаване, започвайки от основния възел. BFS за графика е подобен на този на дърво, с изключение на това, че графиките могат да имат цикли. За разлика от търсенето в дълбочина, всички съседни възли на дадена дълбочина се изследват, преди да се премине към следващото ниво.
BFS алгоритъм
Следват стъпките, включени в използването на търсене в ширина за изследване на графика:
- Вземете данните за матрицата на съседство на графиката или списъка на съседство.
- Създайте опашка и я напълнете с елементи.
- Активирайте основния възел (което означава, че получавате основния възел в началото на опашката).
- Премахнете главата на опашката (или началния елемент), след което поставете в опашката всички близки възли на опашката отляво надясно. Просто извадете главата от опашката и възобновете операцията, ако даден възел няма близки възли, които трябва да бъдат проучени. (Забележка: Ако се появи съсед, който преди това е бил проучен или е в опашката, не го поставяйте в опашка; вместо това го пропуснете.)
- Продължете по този начин, докато опашката се изпразни.
BFS приложения
Поради гъвкавостта на алгоритъма, търсенето в ширина е доста полезно в реалния свят. Това са някои от тях:
- В peer-to-peer мрежа се откриват равноправни възли. Повечето торент клиенти, като BitTorrent, uTorrent и qBittorent, използват този процес за намиране на „семена“ и „връстници“ в мрежата.
- Индексът е изграден с помощта на техники за обхождане на графики при обхождане на мрежата. Процедурата започва със страницата източник като основен възел и преминава надолу към всички вторични страници, които са свързани към страницата източник (и този процес продължава). Поради намалената дълбочина на дървото на рекурсия, търсенето първо в ширина има присъщо предимство тук.
- Използването на GPS навигационни системи, които използват GPS, провеждат търсене в ширина, за да открият близките сайтове.
- Техниката на Чейни, която използва концепцията за търсене в ширина, се използва за събиране на боклук.
Примерно преминаване на BFS
За да започнете, нека разгледаме един прост пример. Ще започнем с 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)
Опашка
анонимна функция на java
| 5 |
Стъпка 7: Изваждане от опашката (5)
Опашка
Сега опашката е празна, така че ще спрем процеса.
Java програма за търсене в ширина
Има няколко подхода за работа с кода. Ще обсъдим най-вече стъпките, включени в прилагането на първо търсене в ширина в Java. Списък на съседство или матрица на съседство могат да се използват за съхраняване на графики; и двата метода са приемливи. Списъкът със съседство ще бъде използван за представяне на нашата графика в нашия код. Когато внедряваме алгоритъма за търсене първо в ширина в Java, е много по-лесно да се справим със списъка за съседство, тъй като трябва само да преминем през списъка с възли, прикрепени към всеки възел, след като възелът бъде изваден от опашката от главата (или началото) на опашка.
Графиката, използвана за демонстриране на кода, ще бъде идентична с тази, използвана в предишния пример.
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;>