В тази статия ще обсъдим алгоритъма BFS в структурата на данните. Търсенето в ширина е алгоритъм за обхождане на графика, който започва обхождането на графиката от основния възел и изследва всички съседни възли. След това избира най-близкия възел и изследва всички неизследвани възли. Докато използвате BFS за обхождане, всеки възел в графиката може да се счита за основен възел.
Има много начини за обхождане на графиката, но сред тях BFS е най-често използваният подход. Това е рекурсивен алгоритъм за търсене във всички върхове на дърво или графична структура от данни. BFS поставя всеки връх на графиката в две категории - посетени и непосетени. Той избира единичен възел в графика и след това посещава всички възли, съседни на избрания възел.
Приложения на BFS алгоритъм
Приложенията на алгоритъма първо в ширина са дадени, както следва -
- BFS може да се използва за намиране на съседните местоположения от дадено местоположение на източника.
- В peer-to-peer мрежа BFS алгоритъмът може да се използва като метод за обхождане за намиране на всички съседни възли. Повечето торент клиенти, като BitTorrent, uTorrent и др., използват този процес, за да намерят „семена“ и „връстници“ в мрежата.
- BFS може да се използва в уеб роботи за създаване на индекси на уеб страници. Това е един от основните алгоритми, които могат да се използват за индексиране на уеб страници. Започва да преминава от изходната страница и следва връзките, свързани със страницата. Тук всяка уеб страница се счита за възел в графиката.
- BFS се използва за определяне на най-краткия път и минималното обхващащо дърво.
- BFS също се използва в техниката на Чейни за дублиране на събирането на отпадъци.
- Може да се използва в метода на Ford-Fulkerson за изчисляване на максималния дебит в потокова мрежа.
Алгоритъм
Стъпките, включени в алгоритъма BFS за изследване на графика, са дадени както следва -
Етап 1: SET STATUS = 1 (състояние на готовност) за всеки възел в G
Стъпка 2: Поставете в опашката началния възел A и задайте неговия СТАТУТ = 2 (състояние на изчакване)
Стъпка 3: Повторете стъпки 4 и 5, докато QUEUE се изпразни
Стъпка 4: Извадете от опашката възел N. Обработете го и задайте неговия СТАТУТ = 3 (обработено състояние).
Стъпка 5: Поставете всички съседи на N, които са в състояние на готовност (чийто СТАТУС = 1) и задайте
техният СТАТУТ = 2
(състояние на изчакване)
[КРАЙ НА ЦИКЪЛА]
Стъпка 6: ИЗХОД
Пример за BFS алгоритъм
Сега нека разберем работата на алгоритъма BFS, като използваме пример. В примера, даден по-долу, има насочен граф със 7 върха.
глобални променливи js
В горната графика минималният път „P“ може да бъде намерен чрез използване на BFS, който ще започне от възел A и ще завърши при възел E. Алгоритъмът използва две опашки, а именно QUEUE1 и QUEUE2. QUEUE1 съдържа всички възли, които трябва да бъдат обработени, докато QUEUE2 съдържа всички възли, които се обработват и изтриват от QUEUE1.
Сега нека започнем да изследваме графиката, започвайки от възел A.
Етап 1 - Първо добавете A към queue1 и NULL към queue2.
QUEUE1 = {A} QUEUE2 = {NULL} Стъпка 2 - Сега изтрийте възел A от queue1 и го добавете в queue2. Вмъкнете всички съседи на възел A в queue1.
QUEUE1 = {B, D} QUEUE2 = {A} Стъпка 3 - Сега изтрийте възел B от queue1 и го добавете в queue2. Вмъкнете всички съседи на възел B в queue1.
QUEUE1 = {D, C, F} QUEUE2 = {A, B} Стъпка 4 - Сега изтрийте възел D от queue1 и го добавете в queue2. Вмъкнете всички съседи на възел D в queue1. Единственият съсед на възел D е F, тъй като вече е вмъкнат, така че няма да бъде вмъкнат отново.
QUEUE1 = {C, F} QUEUE2 = {A, B, D} Стъпка 5 - Изтрийте възел C от queue1 и го добавете в queue2. Вмъкнете всички съседи на възел C в queue1.
QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} Стъпка 5 - Изтрийте възел F от queue1 и го добавете в queue2. Вмъкнете всички съседи на възел F в queue1. Тъй като всички съседи на възел F вече присъстват, няма да ги вмъкваме отново.
QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} Стъпка 6 - Изтриване на възел E от queue1. Тъй като всички негови съседи вече са добавени, няма да ги вмъкваме отново. Сега всички възли са посетени и целевият възел E се среща в queue2.
QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} Сложност на BFS алгоритъм
Времевата сложност на BFS зависи от структурата на данните, използвана за представяне на графиката. Времевата сложност на алгоритъма BFS е O(V+E) , тъй като в най-лошия случай алгоритъмът на BFS изследва всеки възел и ръб. В една графа броят на върховете е O(V), докато броят на ръбовете е O(E).
Пространствената сложност на BFS може да се изрази като O(V) , където V е броят на върховете.
Внедряване на BFS алгоритъм
Сега нека видим изпълнението на BFS алгоритъма в java.
В този код използваме списъка със съседство, за да представим нашата графика. Прилагането на алгоритъма за търсене първо в ширина в Java прави много по-лесно справянето със списъка за съседство, тъй като трябва да преминем през списъка с възли, прикрепени към всеки възел, след като възелът бъде изваден от опашката от главата (или началото) на опашката.
В този пример графиката, която използваме, за да демонстрираме кода, е дадена по следния начин -
import java.io.*; import java.util.*; public class BFSTraversal { private int vertex; /* total number number of vertices in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { vertex = v; adj = new LinkedList[vertex]; 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[vertex]; 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(10); graph.insertedge(0, 1); 2); 3); graph.insertedge(1, graph.insertedge(2, 4); graph.insertedge(3, 5); 6); graph.insertedge(4, 7); graph.insertedge(5, graph.insertedge(6, graph.insertedge(7, 8); system.out.println('breadth first traversal is:'); graph.bfs(2); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/64/bfs-algorithm-3.webp" alt="Breadth First Search Algorithm"> <h3>Conclusion</h3> <p>In this article, we have discussed the Breadth-first search technique along with its example, complexity, and implementation in java programming language. Here, we have also seen the real-life applications of BFS that show it the important data structure algorithm.</p> <p>So, that's all about the article. Hope, it will be helpful and informative to you.</p> <hr></v;>