Пошук спочатку в ширину (BFS) є фундаментальним алгоритм обходу графа . Він передбачає відвідування всіх зв’язаних вузлів графа порівневим способом. У цій статті ми розглянемо концепцію BFS і як це можна ефективно застосувати до графіків
Зміст
- Пошук спочатку в ширину або BFS для графіка
- Зв’язок між BFS для графіка та BFS для дерева
- Пошук спочатку в ширину (BFS) для алгоритму графа
- Як працює алгоритм BFS?
- Реалізація BFS для Graph з використанням списку суміжності
- Складність алгоритму пошуку в ширину (BFS).
- Застосування BFS у графах
- Проблеми з пошуком у ширину або BFS для графа
- Поширені запитання щодо пошуку в ширину (BFS) для графіка
Пошук спочатку в ширину (BFS) для графіка:
Пошук спочатку в ширину (BFS) це алгоритм обходу графа, який досліджує всі вершини в графі на поточній глибині перед тим, як перейти до вершин на наступному рівні глибини. Він починається з визначеної вершини та відвідує всіх своїх сусідів, перш ніж перейти до наступного рівня сусідів. BFS зазвичай використовується в алгоритмах для пошуку шляху, пов’язаних компонентів і проблем найкоротшого шляху в графах.
Зв’язок між BFS для графіка та BFS для дерева:
Обхід у ширину (BFS) для графіка подібний до Обхід дерева в ширину .
Єдина заковика тут полягає в тому, що на відміну від дерева , графіки може містити цикли, тому ми можемо повернутися до того самого вузла знову. Щоб уникнути обробки вузла більше одного разу, ми розділяємо вершини на дві категорії:
монітор з електронно-променевою трубкою
- Відвідали і
- Не відвідував.
Булевий відвіданий масив використовується для позначення відвіданих вершин. Для простоти передбачається, що всі вершини досяжні з початкової вершини. BFS використовує a Пошук спочатку в ширину (BFS) для алгоритму графа:
Давайте обговоримо алгоритм для BFS:
- Ініціалізація: Поставте початковий вузол у чергу та позначте його як відвіданий.
- Розвідка: Поки черга не порожня:
- Видаліть вузол із черги та відвідайте його (наприклад, надрукуйте його значення).
- Для кожного невідвіданого сусіда вилученого з черги вузла:
- Поставте сусіда в чергу.
- Позначити сусіда як відвіданого.
- Припинення: Повторюйте крок 2, доки черга не буде порожньою.
Цей алгоритм гарантує, що всі вузли в графі відвідуються в ширину, починаючи з початкового вузла.
Як працює алгоритм BFS?
Починаючи з кореня, спочатку відвідуються всі вузли на певному рівні, а потім вузли наступного рівня, доки не будуть відвідані всі вузли.
Для цього використовується черга. Усі сусідні невідвідані вузли поточного рівня вставляються в чергу, а вузли поточного рівня позначаються як відвідані та видаляються з черги.
Ілюстрація:
Зрозуміємо роботу алгоритму на наступному прикладі.
Крок 1: Спочатку черга та відвідані масиви порожні.
Черга та відвідані масиви спочатку порожні.
Крок 2: Вставте вузол 0 у чергу та позначте його відвіданим.
Вставте вузол 0 у чергу та позначте його відвіданим.
крок 3: Видаліть вузол 0 з початку черги, відвідайте невідвіданих сусідів і помістіть їх у чергу.
баш еліфВидалити вузол 0 із початку черги та відвідати невідвіданих сусідів і помістити в чергу.
крок 4: Видаліть вузол 1 із початку черги, відвідайте невідвіданих сусідів і помістіть їх у чергу.
Видаліть вузол 1 з початку черги та відвідайте невідвіданих сусідів і натисніть
крок 5: Видаліть вузол 2 із початку черги, відвідайте невідвіданих сусідів і помістіть їх у чергу.
Видаліть вузол 2 із початку черги, відвідайте невідвіданих сусідів і помістіть їх у чергу.
Крок 6: Видаліть вузол 3 з початку черги, відвідайте невідвіданих сусідів і помістіть їх у чергу.
Оскільки ми бачимо, що всі сусіди вузла 3 відвідуються, тому перейдіть до наступного вузла, який стоїть на початку черги.Видаліть вузол 3 з початку черги, відвідайте невідвіданих сусідів і помістіть їх у чергу.
кроки 7: Видаліть вузол 4 з початку черги, відвідайте невідвіданих сусідів і помістіть їх у чергу.
Як ми бачимо, відвідуються всі сусіди вузла 4, тому перейдіть до наступного вузла, який стоїть на початку черги.Видаліть вузол 4 з початку черги, відвідайте невідвіданих сусідів і помістіть їх у чергу.
довго нанизуватиТепер черга стає порожньою, тому припиніть цей процес ітерації.
Реалізація BFS для Graph з використанням списку суміжності:
C++ #include #include #include using namespace std; // Function to perform Breadth First Search on a graph // represented using adjacency list void bfs(vector>& adjList, int startNode, вектор & visited) { // Створення черги для черги BFS q; // Позначити поточний вузол як відвіданий і поставити його в чергу visited[startNode] = true; q.push(startNode); // Ітерація по черзі while (!q.empty()) { // Вилучення вершини з черги та друк її int currentNode = q.front(); q.pop(); cout<< currentNode << ' '; // Get all adjacent vertices of the dequeued vertex // currentNode If an adjacent has not been visited, // then mark it visited and enqueue it for (int neighbor : adjList[currentNode]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } } // Function to add an edge to the graph void addEdge(vector>& adjList, int u, int v) { adjList[u].push_back(v); } int main() { // Кількість вершин у графі int vertices = 5; // Представлення списку суміжності вектора графа> adjList(вершини); // Додаємо ребра до графа addEdge(adjList, 0, 1); addEdge(adjList, 0, 2); addEdge(adjList, 1, 3); addEdge(adjList, 1, 4); addEdge(adjList, 2, 4); // Позначити всі вершини як невідвіданий вектор відвідав (вершини, false); // Виконати обхід BFS, починаючи з вершини 0 cout<< 'Breadth First Traversal starting from vertex ' '0: '; bfs(adjList, 0, visited); return 0; }>
C #include #include #define MAX_VERTICES 100 // Structure to represent a node in adjacency list struct Node { int data; struct Node* next; }; // Function to create a new node struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->дані = дані; newNode->next = NULL; повернути новий вузол; } // Функція для додавання ребра до графа void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v); newNode->next = adjList[u]; adjList[u] = новийвузол; } // Функція для виконання пошуку в ширину на графі // представленому за допомогою списку суміжності void bfs(struct Node* adjList[], int vertices, int startNode, int visited[]) { // Створення черги для BFS int queue[ MAX_VERTICES]; int front = 0, rear = 0; // Позначити поточний вузол як відвіданий і поставити його в чергу visited[startNode] = 1; queue[rear++] = startNode; // Ітерація по черзі while (front != rear) { // Вилучення вершини з черги та друк її int currentNode = queue[front++]; printf('%d ', currentNode); // Отримати всі суміжні вершини вилученої з черги вершини // currentNode Якщо суміжну вершину не було відвідано, // позначте її як відвідану та поставте в чергу struct Node* temp = adjList[currentNode]; while (temp != NULL) { int сусід = temp->data; if (!visited[neighbor]) { visited[neighbor] = 1; queue[rear++] = сусід; } temp = temp->next; } } } int main() { // Кількість вершин у графі int vertices = 5; // Представлення списку суміжності графа struct Node* adjList[vertices]; для (int i = 0; i< vertices; ++i) adjList[i] = NULL; // Add edges to the graph addEdge(adjList, 0, 1); addEdge(adjList, 0, 2); addEdge(adjList, 1, 3); addEdge(adjList, 1, 4); addEdge(adjList, 2, 4); // Mark all the vertices as not visited int visited[vertices]; for (int i = 0; i < vertices; ++i) visited[i] = 0; // Perform BFS traversal starting from vertex 0 printf( 'Breadth First Traversal starting from vertex 0: '); bfs(adjList, vertices, 0, visited); return 0; }> Java import java.util.LinkedList; import java.util.Queue; // Class to represent a graph using adjacency list class Graph { int vertices; LinkedList [] adjList; @SuppressWarnings('unchecked') Graph(int vertices) { this.vertices = vertices; adjList = новий LinkedList[вершини]; для (int i = 0; i< vertices; ++i) adjList[i] = new LinkedList(); } // Function to add an edge to the graph void addEdge(int u, int v) { adjList[u].add(v); } // Function to perform Breadth First Search on a graph // represented using adjacency list void bfs(int startNode) { // Create a queue for BFS Queue queue = new LinkedList(); boolean[] відвіданий = новий boolean[вершини]; // Позначити поточний вузол як відвіданий і поставити його в чергу visited[startNode] = true; queue.add(startNode); // Ітерація по черзі while (!queue.isEmpty()) { // Вилучення вершини з черги та друк її int currentNode = queue.poll(); System.out.print(currentNode + ' '); // Отримати всі суміжні вершини виведеної з черги // вершини currentNode Якщо суміжну вершину // не було відвідано, позначте її як відвідану та // поставте в чергу для (int neighbor : adjList[currentNode]) { if (!visited[neighbor] ) { visited[neighbor] = true; queue.add(сусід); } } } } } public class Main { public static void main(String[] args) { // Кількість вершин у графі int vertices = 5; // Створення графа Graph graph = new Graph(vertices); // Додаємо ребра до графа graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(1, 4); graph.addEdge(2, 4); // Виконати обхід BFS, починаючи з вершини 0 System.out.print( 'Перший обхід ширини, починаючи з вершини 0: '); graph.bfs(0); } }> Python3 from collections import deque # Function to perform Breadth First Search on a graph # represented using adjacency list def bfs(adjList, startNode, visited): # Create a queue for BFS q = deque() # Mark the current node as visited and enqueue it visited[startNode] = True q.append(startNode) # Iterate over the queue while q: # Dequeue a vertex from queue and print it currentNode = q.popleft() print(currentNode, end=' ') # Get all adjacent vertices of the dequeued vertex # If an adjacent has not been visited, then mark it visited and enqueue it for neighbor in adjList[currentNode]: if not visited[neighbor]: visited[neighbor] = True q.append(neighbor) # Function to add an edge to the graph def addEdge(adjList, u, v): adjList[u].append(v) def main(): # Number of vertices in the graph vertices = 5 # Adjacency list representation of the graph adjList = [[] for _ in range(vertices)] # Add edges to the graph addEdge(adjList, 0, 1) addEdge(adjList, 0, 2) addEdge(adjList, 1, 3) addEdge(adjList, 1, 4) addEdge(adjList, 2, 4) # Mark all the vertices as not visited visited = [False] * vertices # Perform BFS traversal starting from vertex 0 print('Breadth First Traversal starting from vertex 0:', end=' ') bfs(adjList, 0, visited) if __name__ == '__main__': main()> C# using System; using System.Collections.Generic; // Class to represent a graph using adjacency list class Graph { int vertices; List [] adjList; public Graph(int vertices) { this.vertices = vertices; adjList = новий список [вершини]; для (int i = 0; i< vertices; ++i) adjList[i] = new List (); } // Функція для додавання ребра до графа public void AddEdge(int u, int v) { adjList[u].Add(v); } // Функція для виконання пошуку в ширину на графіку // представленому за допомогою списку суміжності public void BFS(int startNode) { // Створення черги для черги BFS queue = нова черга (); bool[] відвідано = нові bool[вершини]; // Позначити поточний вузол як відвіданий і поставити його в чергу visited[startNode] = true; queue.Enqueue(startNode); // Ітерація по черзі while (queue.Count != 0) { // Вилучення вершини з черги та друк її int currentNode = queue.Dequeue(); Console.Write(currentNode + ' '); // Отримати всі суміжні вершини виведеної з черги // вершини currentNode Якщо суміжну вершину // не було відвідано, позначте її як відвідану та // поставте в чергу foreach(int neighbor in adjList[currentNode]) { if (!visited[neighbor] ) { visited[neighbor] = true; queue.Enqueue(neighbor); } } } } } class MainClass { public static void Main(string[] args) { // Кількість вершин у графі int vertices = 5; // Створення графа Graph graph = new Graph(vertices); // Додаємо ребра до графа graph.AddEdge(0, 1); graph.AddEdge(0, 2); graph.AddEdge(1, 3); graph.AddEdge(1, 4); graph.AddEdge(2, 4); // Виконати обхід BFS, починаючи з вершини 0 Console.Write( 'Перший обхід ширини, починаючи з вершини 0: '); graph.BFS(0); } }> Javascript // Class to represent a graph using adjacency list class Graph { constructor() { this.adjList = {}; } // Function to add an edge to the graph addEdge(u, v) { if (!this.adjList[u]) this.adjList[u] = []; this.adjList[u].push(v); } // Function to perform Breadth First Search on a graph represented using adjacency list bfs(startNode) { // Create a queue for BFS const queue = []; const visited = new Array(Object.keys(this.adjList).length).fill(false); // Mark the current node as visited and enqueue it visited[startNode] = true; queue.push(startNode); // Iterate over the queue while (queue.length !== 0) { // Dequeue a vertex from queue and print it const currentNode = queue.shift(); console.log(currentNode + ' '); // Get all adjacent vertices of the dequeued vertex currentNode // If an adjacent has not been visited, then mark it visited and enqueue it for (const neighbor of this.adjList[currentNode] || []) { if (!visited[neighbor]) { visited[neighbor] = true; queue.push(neighbor); } } } } } // Create a graph const graph = new Graph(); // Add edges to the graph graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(1, 4); graph.addEdge(2, 4); // Perform BFS traversal starting from vertex 0 console.log('Breadth First Traversal starting from vertex 0: '); graph.bfs(0);> Вихід
Breadth First Traversal starting from vertex 0: 0 1 2 3 4>
Часова складність: O(V+E), де V — кількість вузлів, а E — кількість ребер.
Допоміжний простір: O(V)
Алгоритм аналізу складності пошуку в ширину (BFS):
Часова складність алгоритму BFS: O(V + E)
- BFS досліджує всі вершини та ребра в графі. У гіршому випадку він відвідує кожну вершину та ребро один раз. Таким чином, часова складність BFS дорівнює O(V + E), де V і E є кількістю вершин і ребер у заданому графі.
Просторова складність алгоритму BFS: O(V)
- BFS використовує чергу для відстеження вершин, які потрібно відвідати. У гіршому випадку черга може містити всі вершини графа. Отже, просторова складність BFS дорівнює O(V), де V і E – кількість вершин і ребер у даному графі.
Застосування BFS у графах:
BFS має різні застосування в теорії графів та інформатиці, зокрема:
- Пошук найкоротшого шляху: BFS можна використовувати для пошуку найкоротшого шляху між двома вузлами в незваженому графі. Відстежуючи батьківський вузол під час обходу, можна відновити найкоротший шлях.
- Виявлення циклу: BFS можна використовувати для виявлення циклів у графі. Якщо вузол відвідується двічі під час обходу, це вказує на наявність циклу.
- Підключені компоненти: BFS можна використовувати для ідентифікації пов’язаних компонентів у графі. Кожен зв'язаний компонент - це набір вузлів, до яких можна дістатися один від одного.
- Топологічне сортування: BFS можна використовувати для виконання топологічного сортування на спрямованому ациклічному графі (DAG). Топологічне сортування розташовує вузли в лінійному порядку таким чином, що для будь-якого ребра (u, v) u з’являється перед v у порядку.
- Обхід порядку рівня бінарних дерев: BFS може використовуватися для виконання обходу порядку рівня бінарного дерева. Цей обхід відвідує всі вузли на одному рівні перед переходом на наступний рівень.
- Маршрутизація мережі: BFS можна використовувати для пошуку найкоротшого шляху між двома вузлами в мережі, що робить його корисним для маршрутизації пакетів даних у мережевих протоколах.
Проблеми з пошуком у ширину або BFS для графіка:
| Так ні | Проблеми | Практика |
|---|---|---|
| 1. | Знайдіть рівень даного вузла в неорієнтованому графі | Посилання |
| 2. | Мінімізуйте максимальну суміжну різницю на шляху від верхнього лівого до нижнього правого кута | Посилання |
| 10. | Перевірте, чи доступний пункт призначення заданої матриці з потрібними значеннями клітинок | Посилання |
Поширені запитання щодо пошуку в ширину (BFS) для графіка:
Питання 1: Що таке BFS і як він працює?
відповідь: BFS — це алгоритм обходу графа, який систематично досліджує граф, відвідуючи всі вершини на заданому рівні перед переходом на наступний рівень. Він починається з початкової вершини, поміщає її в чергу та позначає як відвідану. Потім він виключає вершину з черги, відвідує її та додає до черги всіх її невідвіданих сусідів. Цей процес триває, доки черга не буде порожньою.
Питання 2: Які програми BFS?
відповідь: BFS має різні програми, зокрема пошук найкоротшого шляху в незваженому графі, виявлення циклів у графі, топологічне сортування орієнтованого ациклічного графа (DAG), пошук пов’язаних компонентів у графі та розв’язування таких головоломок, як лабіринти та судоку.
вимкнути режим розробника
Питання 3: Яка часова складність BFS?
відповідь: Часова складність BFS дорівнює O(V + E), де V — кількість вершин, а E — кількість ребер у графі.
Питання 4: Яка космічна складність BFS?
відповідь: Просторова складність BFS становить O(V), оскільки він використовує чергу для відстеження вершин, які потрібно відвідати.
Питання 5: Які переваги використання BFS?
відповідь: BFS простий у реалізації та ефективний для пошуку найкоротшого шляху в незваженому графі. Це також гарантує відвідування всіх вершин графа.
Пов'язані статті:
- Останні статті про BFS
- Перший обхід глибини
- Застосування обходу в ширину
- Застосування пошуку в глибину
- Часова та просторова складність пошуку в ширину (BFS)