Меню

Програма першого пошуку (BFS) C ++ для обходу графіка чи дерева

  • Головна
  • Інший
  • Програма першого пошуку (BFS) C ++ для обходу графіка чи дерева

breadth first search c program traverse graph

Спробуйте Наш Інструмент Для Усунення Проблем

Цей підручник охоплює широту першого пошуку в C ++, в якій графік або дерево обводиться в ширину. Ви також дізнаєтесь алгоритм та реалізацію BFS:

Цей явний підручник на C ++ дасть вам детальне пояснення методів обходу, які можна виконати на дереві або графіку.

Обхід - це техніка, за допомогою якої ми відвідуємо кожен вузол графіка або дерева. Існує два стандартних методи обходу.

  • Пошук по ширині (BFS)
  • Пошук по глибині (DFS)

=> Дивіться тут, щоб ознайомитися з повним списком підручників з C ++.

що таке пов'язаний список c ++

Широкий пошук у C ++

Що ви дізнаєтесь:

Техніка широкого пошуку (BFS) у C ++

У цьому навчальному посібнику ми детально обговоримо техніку пошуку, що стосується найпершого розмаху.

У техніці обходу першої ширини графік або дерево обводиться вшир. Цей метод використовує структуру даних черги для зберігання вершин або вузлів, а також для визначення, яку вершину / вузол слід взяти наступним.

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

Широкий алгоритм пошуку

Нижче наведено алгоритм техніки BFS.

Розглянемо G як графік, який ми збираємось пройти, використовуючи алгоритм BFS.

Нехай S є кореневим / початковим вузлом графіка.

  • Крок 1: Почніть з вузла S і поставте його в чергу до черги.
  • Крок 2: Повторіть наступні кроки для всіх вузлів на графіку.
  • Крок 3: Знесіть із S і обробіть його.
  • Крок 4: Викладіть у чергу всі сусідні вузли S і обробіть їх.
  • (КІНЕЦЬ ЦИКЛУ)
  • Крок 6: ВИХІД

Псевдокод

Псевдокод для техніки BFS наведено нижче.

Procedure BFS (G, s) G is the graph and s is the source node begin let q be queue to store nodes q.enqueue(s) //insert source node in the queue mark s as visited. while (q is not empty) //remove the element from the queue whose adjacent nodes are to be processed n = q.dequeue( ) //processing all the adjacent nodes of n for all neighbors m of n in Graph G if w is not visited q.enqueue (m) //Stores m in Q to in turn visit its adjacent nodes mark m as visited. end

Обхід з ілюстраціями

Ілюстрації BFS Крок 1

Нехай 0 - початковий вузол або вузол джерела. По-перше, ми ставимо його в чергу у відвідану чергу та всі прилеглі до неї вузли в черзі.

BFS Illustrations Крок 2

Далі ми беремо на обробку один із сусідніх вузлів, тобто 1. Позначаємо його як відвіданий, видаляючи з черги і ставимо сусідні вузли в чергу (2 і 3 вже в черзі). Оскільки 0 вже відвідано, ми його ігноруємо.

найкращий завантажувач пісень mp3 для android

BFS Illustrations Крок 3

Далі ми скидаємо вузол 2 із гри та позначаємо його як відвіданий. Потім сусідній вузол 4 додається до черги.

BFS Illustrations Крок 4

Далі ми виводимо з черги номер 3 і позначаємо його як відвідане. Вузол 3 має лише один сусідній вузол, тобто 0, який вже відвідано. Отже, ми це ігноруємо.

Ілюстрації BFS Крок 5

На цьому етапі в черзі присутній лише вузол 4. Сусідній вузол 2 уже відвіданий, отже, ми його ігноруємо. Зараз ми відзначаємо 4 як відвідані.

Ілюстрації BFS Крок 6

Далі послідовність, присутня у переглянутому списку, є першим обходом даного графіка.

Якщо ми спостерігаємо за даним графіком та послідовністю обходу, ми можемо помітити, що для алгоритму BFS ми дійсно переходимо графік ушир і переходимо до наступного рівня.

Впровадження BFS

#include #include using namespace std; // a directed graph class class DiGraph { int V; // No. of vertices // Pointer to an array containing adjacency lists list *adjList; public: DiGraph(int V); // Constructor // add an edge from vertex v to w void addEdge(int v, int w); // BFS traversal sequence starting with s ->starting node void BFS(int s); }; DiGraph::DiGraph(int V) { this->V = V; adjList = new list (V); } void DiGraph::addEdge(int v, int w) { adjList(v).push_back(w); // Add w to v’s list. } void DiGraph::BFS(int s) { // initially none of the vertices is visited bool *visited = new bool(V); for(int i = 0; i queue; // Mark the current node as visited and enqueue it visited(s) = true; queue.push_back(s); // iterator 'i' to get all adjacent vertices list ::iterator i; while(!queue.empty()) { // dequeue the vertex s = queue.front(); cout << s << ' '; queue.pop_front(); // get all adjacent vertices of popped vertex and process each if not already visited for (i = adjList(s).begin(); i != adjList(s).end(); ++i) { if (!visited(*i)) { visited(*i) = true; queue.push_back(*i); } } } } // main program int main() { // create a graph DiGraph dg(5); dg.addEdge(0, 1); dg.addEdge(0, 2); dg.addEdge(0, 3); dg.addEdge(1, 2); dg.addEdge(2, 4); dg.addEdge(3, 3); dg.addEdge(4, 4); cout << 'Breadth First Traversal for given graph (with 0 as starting node): '<

Вихід:

безкоштовне програмне забезпечення для конвертації відео для Windows 10

Обхід першої ширини для даного графіка (з 0 як початковий вузол):

0 1 2 3 4

Ми застосували BFS у вищезазначеній програмі. Зверніть увагу, що графік має форму списку суміжності, і тоді ми використовуємо ітератор для перегляду списку та виконання BFS.

Ми використали той самий графік, який використовували для ілюстративних цілей, як вхід до програми для порівняння послідовності обходу.

Аналіз виконання

Якщо V - кількість вершин, а E - кількість ребер графіка, то складність часу для BFS може бути виражена як O (| V | + | E |) . Сказавши це, це також залежить від структури даних, яку ми використовуємо для представлення графіка.

Якщо ми використовуємо список суміжностей (як у нашому впровадженні), то складність часу становить O (| V | + | E |).

Якщо ми використовуємо матрицю суміжності, то складність часу така O (V ^ 2) .

Окрім використовуваних структур даних, існує також фактор, чи є графік густо заповненим чи малонаселеним.

Коли кількість вершин перевищує кількість ребер, тоді графік називається розрідженим, оскільки там буде багато роз’єднаних вершин. У цьому випадку часова складність графіка становитиме O (V).

З іншого боку, іноді графік може мати більшу кількість ребер, ніж кількість вершин. У такому випадку графік називають густо заповненим. Складність у часі такого графіка дорівнює O (E).

На закінчення, що означає вираз O (| V | + | E |), залежить від того, щільно чи малозаселено графік, домінуючий фактор, тобто ребра або вершини, відповідно визначатимуть часову складність графіка.

Застосування BFS Traversal

  • Вивіз сміття: Техніка вивезення сміття, «алгоритм Чейні», використовує обхід для кодування копіювання збору сміття.
  • Трансляція в мережах: Пакет переходить від одного вузла до іншого за допомогою техніки BFS в мережі мовлення, щоб дістатися до всіх вузлів.
  • GPS навігація: Ми можемо використовувати BFS в GPS-навігації, щоб знайти всі сусідні або сусідні вузли розташування.
  • Веб-сайти соціальних мереж: Враховуючи особу «P», ми можемо знайти всіх людей на відстані, «d» від p, використовуючи BFS до рівня d.
  • Партнерські мережі: Знову BFS можна використовувати в однорангових мережах для пошуку всіх сусідніх вузлів.
  • Найкоротший шлях та мінімальне розмахувальне дерево на незваженому графіку: Метод BFS використовується для пошуку найкоротшого шляху, тобто шляху з найменшою кількістю ребер у незваженому графіку. Подібним чином ми також можемо знайти мінімальне дерево, що охоплює, за допомогою BFS на незваженому графіку.

Висновок

Техніка пошуку на широту - це метод, який використовується для обходу всіх вузлів графіка чи дерева в широту.

Ця техніка в основному використовується для пошуку найкоротшого шляху між вузлами графа або в додатках, які вимагають від нас відвідування кожного сусіднього вузла, як у мережах.

=> Клацніть тут для безкоштовного курсу C ++.

Рекомендована література

^