У цій статті ми обговоримо алгоритм BFS у структурі даних. Пошук у ширину — це алгоритм обходу графа, який починає обхід графа з кореневого вузла та досліджує всі сусідні вузли. Потім він вибирає найближчий вузол і досліджує всі недосліджені вузли. Під час використання BFS для обходу будь-який вузол у графі можна вважати кореневим вузлом.
Існує багато способів обходу графіка, але серед них підхід BFS є найпоширенішим. Це рекурсивний алгоритм для пошуку всіх вершин структури даних дерева або графа. BFS поділяє кожну вершину графа на дві категорії - відвідані та невідвідані. Він вибирає один вузол на графіку, а потім відвідує всі вузли, суміжні з вибраним вузлом.
Застосування алгоритму BFS
Застосування алгоритму «спершу в ширину» наведено таким чином:
- BFS можна використовувати для пошуку сусідніх місць із даного джерела.
- У одноранговій мережі алгоритм BFS можна використовувати як метод обходу для пошуку всіх сусідніх вузлів. Більшість торрент-клієнтів, таких як BitTorrent, uTorrent тощо, використовують цей процес для пошуку «початківців» і «однолітків» у мережі.
- BFS можна використовувати в веб-сканерах для створення індексів веб-сторінок. Це один із основних алгоритмів, який можна використовувати для індексації веб-сторінок. Він починає проходити з початкової сторінки та переходить за посиланнями, пов’язаними зі сторінкою. Тут кожна веб-сторінка розглядається як вузол на графіку.
- BFS використовується для визначення найкоротшого шляху та мінімального остовного дерева.
- BFS також використовується в техніці Чейні для дублювання збору сміття.
- Його можна використовувати в методі Форда-Фулкерсона для обчислення максимального потоку в потоковій мережі.
Алгоритм
Кроки, задіяні в алгоритмі BFS для дослідження графа, наведені нижче:
Крок 1: SET STATUS = 1 (стан готовності) для кожного вузла в G
крок 2: Поставте в чергу початковий вузол A та встановіть його STATUS = 2 (стан очікування)
крок 3: Повторюйте кроки 4 і 5, доки ЧЕРГА не буде порожньою
крок 4: Виключіть вузол N з черги. Обробіть його та встановіть для нього STATUS = 3 (стан обробки).
крок 5: Поставте в чергу всіх сусідів N, які знаходяться в стані готовності (чий STATUS = 1) і встановіть
їх СТАТУС = 2
(стан очікування)
[КІНЕЦЬ ЦИКЛУ]
Крок 6: ВИХІД
Приклад алгоритму BFS
Тепер давайте зрозуміємо роботу алгоритму BFS на прикладі. У наведеному нижче прикладі орієнтований граф має 7 вершин.
На наведеному вище графіку мінімальний шлях «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.
дженерики java
QUEUE1 = {B, D} QUEUE2 = {A} Крок 3 - Тепер видаліть вузол B з queue1 і додайте його в queue2. Вставте всіх сусідів вузла B до queue1.
QUEUE1 = {D, C, F} QUEUE2 = {A, B} Крок 4 - Тепер видаліть вузол D із черги1 та додайте його до черги2. Вставте всіх сусідів вузла 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 із черги1 та додати його до черги2. Вставте всіх сусідів вузла F до queue1. Оскільки всі сусіди вузла F вже присутні, ми не будемо вставляти їх знову.
QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} Крок 6 - Видалити вузол E з черги1. Оскільки всі його сусіди вже додані, ми не будемо вставляти їх знову. Тепер усі вузли відвідано, і цільовий вузол E потрапляє в чергу 2.
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;>