Що таке BFS?

Пошук у ширину (BFS) заснований на обході вузлів шляхом додавання сусідів кожного вузла до черги обходу, починаючи з кореневого вузла. BFS для графа подібний до дерева, за винятком того, що графи можуть мати цикли. На відміну від пошуку в глибину, усі сусідні вузли на заданій глибині досліджуються перед переходом до наступного рівня.

hashmap

Алгоритм BFS

Нижче наведено кроки, пов’язані з використанням пошуку в ширину для дослідження графіка:

1. Візьміть дані для матриці суміжності або списку суміжності графіка.
2. Створіть чергу та заповніть її предметами.
3. Активувати кореневий вузол (це означає, що отримати кореневий вузол на початку черги).
4. Видаліть із черги заголовок черги (або початковий елемент), а потім поставте в чергу всі найближчі вузли черги зліва направо. Просто зніміть головку з черги та відновіть операцію, якщо вузол не має поряд вузлів, які потрібно дослідити. (Примітка: якщо з’являється сусід, який раніше досліджувався або знаходиться в черзі, не ставте його в чергу; натомість пропустіть).
5. Продовжуйте таким чином, доки черга не буде порожньою.

Програми BFS

Завдяки гнучкості алгоритму пошук у ширину є досить корисним у реальному світі. Ось деякі з них:

1. У одноранговій мережі виявляються однорангові вузли. Більшість торрент-клієнтів, як-от BitTorrent, uTorrent і qBittorent, використовують цей процес для пошуку «початківців» і «однорангів» у мережі.
2. Індекс створено за допомогою методів обходу графів під час веб-сканування. Процедура починається з вихідної сторінки як кореневого вузла та проходить до всіх вторинних сторінок, пов’язаних із вихідною сторінкою (і цей процес продовжується). Завдяки зменшеній глибині дерева рекурсії пошук у ширину має невід’ємну перевагу.
3. Використання навігаційних систем GPS за допомогою GPS, проведення пошуку вшир, щоб знайти найближчі сайти.
4. Техніка Чейні, яка використовує концепцію пошуку вшир, використовується для збирання сміття.

Приклад BFS Traversal

Для початку розглянемо простий приклад. Ми почнемо з 0 як кореневого вузла і рухатимемося вниз по графіку.

Крок 1: Поставити в чергу (0)

Черга

крок 2: Виключити з черги (0), поставити в чергу (1), поставити в чергу (3), поставити в чергу (4)

Черга

крок 3: Зняти з черги (1), зняти з черги (2)

Черга

крок 4: Видалити з черги(3), Вилучити з черги(5). Ми більше не додамо 1 до черги, оскільки 0 уже досліджено.

Черга

крок 5: Дечерга(4)

Черга

Крок 6: Виключити з черги (2)

Черга

рядок java для char

Крок 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;>