الگوریتم BFS چیست؟ – به زبان ساده + مثال

۴۲۰۷ بازدید
آخرین به‌روزرسانی: ۰۷ تیر ۱۴۰۲
زمان مطالعه: ۱۳ دقیقه
الگوریتم BFS چیست؟ – به زبان ساده + مثال

یکی از موضوعات مهم در مباحث طراحی الگوریتم و برنامه نویسی، روش‌های جستجو در «ساختمان داده‌‌های» (Data Structures) مختلف است. به عبارتی، از الگوریتم‌های جستجو به منظور بازیابی مقادیر خاصی از اطلاعات ذخیره شده در ساختار داده‌های مختلف استفاده می‌شود. الگوریتم «جستجوی اول سطح» (Breadth First Search | BFS) به عنوان یکی از الگوریتم‌های جستجوی رایج برای «گراف» (Graph) و «درخت» (Tree) محسوب می‌شود. در این مطلب از مجله فرادرس قصد داریم به این پرسش پاسخ دهیم که ویژگی‌ها و مزایا و معایب الگوریتم BFS چیست و با ارائه یک مثال ساده، به توضیح مرحله به مرحله این الگوریتم برای پیدا کردن پاسخ مسئله می‌پردازیم.

الگوریتم های پیمایش ساختار داده ها

الگوریتم‌های پیمایش، روشی برای جستجوی یک گره در ساختمان داده‌های درخت و گراف به حساب می‌آیند. درخت و گراف به عنوان ۲ ساختار داده در طراحی الگوریتم و برنامه نویسی محسوب می‌شوند که از آن‌ها می‌توان برای نمایش و نگهداری داده‌ها به نحوی استفاده کرد که ارتباطی بین آن‌ها وجود داشته باشد. این نوع ارتباط در ساختار داده درخت می‌تواند به صورت سلسله‌مراتبی و بدون وجود حلقه باشد و در گراف می‌توان ارتباطی را بین داده‌ها ایجاد کرد که باعث شکل‌گیری حلقه در گراف شود.

به منظور یافتن مقداری خاص در این ۲ نوع ساختار داده، می‌توان از ۲ روال جستجو استفاده کرد:

  • روش «جستجوی اول سطح» (Breadth-First Search) یا همان الگوریتم BFS
  • روش «جستجوی اول عمق» (Depth-First Search) یا الگوریتم DFS

در مطلب حاضر، قصد داریم به روش جستجوی اول سطح بپردازیم و با مثال کاربردی مراحل آن را توضیح دهیم.

الگوریتم BFS چیست ؟

الگوریتم BFS برای جستجوی مقداری خاص در یک درخت یا گراف استفاده می‌شود. روال جستجوی الگوریتم BFS از گره ریشه درخت یا گراف آغاز می‌شود. در هر سطح از درخت یا گراف، تمامی گره‌ها مورد بررسی قرار می‌گیرند و سپس روند جستجو در سطح بعدی این ساختار داده‌ها ادامه پیدا می‌کند. با کمک این الگوریتم می‌توان بدون گیر افتادن در یک حلقه بی‌پایان، هر گره را بررسی کرد.

الگوریتم جستجوی اول سطح از ساختار داده «صف» (Queue) برای پیمایش گراف یا درخت استفاده می‌کند. یکی از اصول ساختار داده صف، اصل «اولین ورودی - اولین خروجی» (First In - First Out | FIFO) است. الگوریتم BFS با استفاده از چنین اصلی، در هر گامی که گره جدیدی را در گراف یا درخت ملاحظه می‌کند،‌ گره‌های مجاور (گره‌های فرزند) آن را در صف قرار می‌دهد و سپس گره‌های موجود در صف را با اصل FIFO برای یافتن پاسخ،‌ بررسی می‌کند. به منظور درک بهتر عملکرد این الگوریتم، در بخش‌های بعدی این مطلب، مثالی کاربردی ارائه کرده‌ایم.

کاربرد الگوریتم جستجوی اول سطح

الگوریتم BFS به عنوان یکی از الگوریتم‌های ساده جستجو محسوب می‌شود و می‌توان به سادگی آن را با استفاده از زبان برنامه نویسی پیاده‌سازی کرد، از این الگوریتم در مسائل مختلف مهمی استفاده می‌شود که در ادامه به برخی از آن‌ها اشاره شده است:

  • کاربرد الگوریتم BFS در پیدا کردن کوتاه‌ترین مسیر پاسخ در گراف غیر وزن‌دار: از آنجایی که الگوریتم BFS سطر به سطر سطح یک درخت را پیمایش می‌کند، این تضمین وجود دارد که کوتاه‌ترین مسیر برای پیدا کردن گره مورد نظر طی شده است.
  • کاربرد الگوریتم جستجوی اول سطح در شبکه‌های نظیر به نظیر «Peer To Peer Networks»: در چنین شبکه‌هایی مانند شبکه BitTorrent از این الگوریتم به منظور پیدا کردن گره‌های همسایه استفاده می‌شود.
  • استفاده از الگوریتم BFS در موتورهای جستجو: «خزشگر» (Crawler) وب از این الگوریتم برای استخراج اطلاعات از صفحات اینترنت استفاده می‌کند. خزشگرها با کمک این روش، از یک صفحه اینترنتی، کار استخراج اطلاعات را شروع می‌کنند و با استفاده از لینک‌های موجود در صفحه اینترنت، روند جستجوی خود را در صفحات لینک داده شده، ادامه می‌دهند.
  • استفاده از الگوریتم جستجوی اول سطح در شبکه‌های اجتماعی: یافتن افراد مختلف در شبکه‌های اجتماعی بر اساس این الگوریتم انجام می‌شود. برای مثال، این الگوریتم افرادی را که با دوستان شما لینک هستند، به شما پیشنهاد می‌دهند تا اگر آن‌ها را می‌شناسید، با آن‌ها ارتباط برقرار کنید.
  • کاربرد الگوریتم BFS در شبکه: از این الگوریتم می‌توان برای انتشار بسته در طول یک شبکه استفاده کرد تا بسته ارسالی به تمامی گره‌ها برسد.
  • تشخیص وجود حلقه در گراف‌های جهت‌دار و غیر جهت‌دار با استفاده از الگوریتم جستجوی اول سطح
  • بررسی تمامی گره‌ها: با استفاده از الگوریتم جستجوی اول سطح می‌توان تمام گره‌هایی را درون گراف یا درخت پیدا کرد که از گره آغازین می‌توان به آن‌ها دسترسی داشت.

تفاوت پیمایش الگوریتم BFS در گراف و درخت چیست ؟

همان‌طور که گفتیم، از الگوریتم جستجوی اول سطح به منظور پیمایش درخت یا گراف برای یافتن مقداری خاص استفاده می‌شود. روال پیمایش الگوریتم BFS در گراف، مشابه با روال جستجوی این الگوریتم در ساختار داده درخت است. تنها نکته‌ای که باید به آن توجه کنیم، این است که گراف می‌تواند شامل حلقه باشد. به همین خاطر، در روال جستجو ممکن است با یک گره بیش از یک بار برخورد کنیم.

به منظور جلوگیری از بازدید یک گره بیش از یک بار، می‌توان دو دسته مجزا برای راس‌های گراف در نظر بگیریم:

  • راس‌های دیده شده
  • راس‌های دیده نشده

برای استفاده از الگوریتم جستجوی اول سطح در پیمایش درخت،‌ چنین شرطی لحاظ نمی‌شود، زیرا ساختار درخت به نحوی است که حلقه در آن ایجاد نمی‌شود. در ادامه مطلب، به مراحل الگوریتم BFS‌ می‌پردازیم و مثال واضحی برای آن ارائه خواهیم کرد.

جستجوی اول سطح

مراحل الگوریتم جستجوی اول سطح چیست ؟

مراحل پیمایش گراف یا درخت را با استفاده از الگوریتم BFS می‌توان در چندین مرحله خلاصه کرد. در ادامه،‌ به توضیح این مراحل می‌پردازیم:

  1. گام اول: گرافی را تعریف کنید که قصد پیمایش آن را با استفاده از الگوریتم BFS‌ دارید.
  2. گام دوم: راس نخست گراف را انتخاب کنید. پیمایش گراف، از این راس آغاز می‌شود.
  3. گام سوم: می‌توان از ساختار داده‌های «آرایه» (Array) و صف برای پیمایش گراف استفاده کرد. آرایه تعریف شده، برای نگهداری راس‌هایی از گراف هستند که با پیمایش گراف، ملاحظه شده‌اند.
  4. گام چهارم: راس اول را به آرایه اضافه کنید. سپس، راس‌های مجاور راس نخست را به ساختار داده صف اضافه کنید.
  5. گام پنجم: از روش «اولین ورودی - اولین خروجی» (First In - First Out | FIFO) برای حذف اولین آیتم موجود در صف استفاده کنید. آیتم خارج شده از صف را درون آرایه قرار دهید و سپس راس‌های مجاور آیتم حذف شده را به صف اضافه کنید.
  6. گام ششم: گام پنجم را آنقدر تکرار کنید تا راسی از گراف باقی نماند.

مثال کاربردی از الگوریتم BFS

در این بخش قصد داریم مثالی ساده برای درک بهتر از عملکر الگوریتم جستجوی BFS ارائه کنیم. بدین منظور، در مرحله اول، گرافی را برای پیمایش تعیین می‌کنیم که در ادامه آن را ملاحظه می‌کنید.

در مرحله دوم، ۲ ساختار داده خالی آرایه و صف ایجاد می‌کنیم.

در مرحله سوم، گره اول گراف را درون صف قرار می‌دهیم و این گره را به عنوان گره ملاحظه شده درون آرایه ذخیره می‌کنیم.

گره ملاحظه شده را از ابتدای صف حذف می‌کنیم و گره‌های مجاور گره حذف شده از صف را درون صف و آرایه قرار می‌دهیم.

گره ۱ را از ابتدای صف حذف و گره مجاور آن را به صف و آرایه اضافه می‌کنیم.

سپس، گره ۲ را از ابتدای صف حذف کرده و گره مجاور آن را به صف و آرایه اضافه می‌کنیم.

گره ۳ را از صف حذف می‌کنیم و اگر گره ۳ دارای گره مجاوری باشد که از قبل، آن گره ملاحظه نشده باشد، آن را به صف و آرایه اضافه می‌کنیم. از آنجایی که گره ۴ به عنوان گره مجاور گره ۳ است و در مراحل قبل، گره ۴ به آرایه اضافه شده بود، مجدداً آن را به آرایه اضافه نمی‌کنیم. بدین‌ترتیب، گره بعدی موجود در صف را حذف می‌کنیم.

پس از حذف گره ۴ از صف، بررسی می‌کنیم آیا گره مجاور جدیدی برای گره ۴ وجود دارد؟ همان‌طور که در تصویر زیر ملاحظه می‌کنید، گره مجاور جدیدی برای گره ۴ موجود نیست و تمامی گره‌های گراف با استفاده از الگوریتم BFS پیمایش شدند. در صورتی که گره‌ای از گراف باقی نمانده باشد، صف مقدارش خالی می‌شود و در این حالت، کار پیمایش الگوریتم BFS‌ به اتمام می‌رسد.

پیچیدگی زمانی و پیچیدگی فضایی الگوریتم جستجوی BFS چیست؟

پیچیدگی زمانی الگوریتم جستجوی BFS را می‌توان به صورت O(|V|+|E|) نشان داد، زیرا این الگوریتم در بدترین شرایط تمامی گره‌های درخت یا گراف را برای یافتن پاسخ مسئله، جستجو می‌کند. |V| تعداد گره‌ها و |E| تعداد یال‌های گراف یا درخت را مشخص می‌کنند. پیچیدگی فضایی الگوریتم جستجوی اول سطح نیز برابر با O(|V|) یا O(b^d) است که |V| تعداد گره‌های گراف یا درخت را تعیین می‌کند و b و d به ترتیب تعداد فرزندان هر گره و عمق درخت را نشان می‌دهند.

مزایای الگوریتم جستجوی اول سطح

الگوریتم جستجوی BFS، الگوریتم ساده‌ای است که به دلیل داشتن مزیت‌های مهم، از آن در حل مسائل مهمی استفاده می‌شود. در ادامه، به برخی از مهم‌ترین مزیت‌های این الگوریتم اشاره شده است:

  • در این روش جستجو، چنانچه تنها یک راه‌حل برای یافتن گره مورد نظر وجود داشته باشد، در نهایت آن گره توسط الگوریتم BFS پیدا خواهد شد.
  • اگر بیش از یک راه برای رسیدن به پاسخ مسئله وجود داشته باشد، الگوریتم جستجوی اول سطح،‌ کوتاه‌ترین راه را پیدا می‌کند.
  • چنانچه ساختار داده‌های درخت یا گراف دارای گره‌های زیادی نباشند، در هنگام استفاده از الگوریتم BFS به حجم زیادی از حافظه نیازی نداریم.
  • پیاده‌سازی این الگوریتم با استفاده از زبان‌های برنامه نویسی، ساده است.

معایب الگوریتم BFS چیست ؟

یکی از مهم‌ترین معایب الگوریتم جستجوی اول سطح یا همان BFS این است که به حجمی از حافظه برای ذخیره‌سازی گره‌های گراف یا درخت احتیاج دارد. میزان حافظه مصرفی نیز به تعداد گره‌های ذخیره شده بستگی دارد. می‌توان گفت میزان پیچیدگی فضای مورد نیاز این الگوریتم، برابر با b به توان d است.

حرف b تعداد فرزندان هر گره را مشخص می‌کند و حرف d برابر با عمیق درخت است. بنابراین، چنانچه تعداد گره‌های گراف یا درخت زیاد باشند، نمی‌توان این روش را بر روی کامپیوترهای معمولی با میزان حافظه پایین اجرا کرد.

پیاده سازی الگوریتم جستجوی اول سطح

در این بخش، نحوه پیاده‌سازی الگوریتم BFS را برای مثال گرافی ملاحظه می‌کنید که در بخش قبل ارائه کردیم. قطعه کدهای ارائه شده به ۶ زبان برنامه نویسی C ،C++‎ ،C#‎ ،جاوا، جاوا اسکریپت و پایتون هستند که خروجی تمامی این قطعه کدها، یکسان است.

پیاده سازی الگوریتم BFS با زبان برنامه نویسی C

در قطعه کد زیر، نحوه پیاده‌سازی الگوریتم جستجوی اول سطح را با زبان برنامه نویسی C ملاحظه می‌کنید.

1#include <stdbool.h>
2#include <stdio.h>
3#include <stdlib.h>
4 
5#define MAX_VERTICES 50
6 
7// This struct represents a directed graph using
8// adjacency list representation
9typedef struct Graph_t {
10     
11    // No. of vertices
12    int V;
13    bool adj[MAX_VERTICES][MAX_VERTICES];
14} Graph;
15 
16// Constructor
17Graph* Graph_create(int V)
18{
19    Graph* g = malloc(sizeof(Graph));
20    g->V = V;
21 
22    for (int i = 0; i < V; i++) {
23        for (int j = 0; j < V; j++) {
24            g->adj[i][j] = false;
25        }
26    }
27 
28    return g;
29}
30 
31// Destructor
32void Graph_destroy(Graph* g) {
33    free(g);
34}
35 
36// function to add an edge to graph
37void Graph_addEdge(Graph* g, int v, int w)
38{
39    // Add w to v’s list.
40    g->adj[v][w] = true;
41}
42 
43// Prints BFS traversal from a given source s
44void Graph_BFS(Graph* g, int s)
45{
46    // Mark all the vertices as not visited
47    bool visited[MAX_VERTICES];
48    for (int i = 0; i < g->V; i++) {
49        visited[i] = false;
50    }
51 
52    // Create a queue for BFS
53    int queue[MAX_VERTICES];
54    int front = 0, rear = 0;
55 
56    // Mark the current node as visited and enqueue it
57    visited[s] = true;
58    queue[rear++] = s;
59 
60    while (front != rear) {
61        // Dequeue a vertex from queue and print it
62        s = queue[front++];
63        printf("%d ", s);
64 
65        // Get all adjacent vertices of the dequeued
66        // vertex s. If a adjacent has not been visited,
67        // then mark it visited and enqueue it
68        for (int adjacent = 0; adjacent < g->V;
69             adjacent++) {
70            if (g->adj[s][adjacent] && !visited[adjacent]) {
71                visited[adjacent] = true;
72                queue[rear++] = adjacent;
73            }
74        }
75    }
76}
77 
78// Driver code
79int main()
80{
81    // Create a graph
82    Graph* g = Graph_create(4);
83    Graph_addEdge(g, 0, 1);
84    Graph_addEdge(g, 0, 2);
85    Graph_addEdge(g, 1, 2);
86    Graph_addEdge(g, 2, 0);
87    Graph_addEdge(g, 2, 3);
88    Graph_addEdge(g, 3, 3);
89 
90    printf("Following is Breadth First Traversal "
91           "(starting from vertex 2) \n");
92    Graph_BFS(g, 2);
93    Graph_destroy(g);
94 
95    return 0;
96}

خروجی قطعه کد بالا را در ادامه ملاحظه می‌کنید:

Following is Breadth First Traversal (starting from vertex 2) 
2 0 3 1 

پیاده سازی الگوریتم BFS با زبان برنامه نویسی C++‎

در قطعه کد زیر، نحوه پیاده‌سازی الگوریتم جستجوی اول سطح را با زبان برنامه نویسی C++‎ ملاحظه می‌کنید.

1// C++ code to print BFS traversal from a given
2// source vertex
3 
4#include <bits/stdc++.h>
5using namespace std;
6 
7// This class represents a directed graph using
8// adjacency list representation
9class Graph {
10 
11    // No. of vertices
12    int V;
13 
14    // Pointer to an array containing adjacency lists
15    vector<list<int> > adj;
16 
17public:
18    // Constructor
19    Graph(int V);
20 
21    // Function to add an edge to graph
22    void addEdge(int v, int w);
23 
24    // Prints BFS traversal from a given source s
25    void BFS(int s);
26};
27 
28Graph::Graph(int V)
29{
30    this->V = V;
31    adj.resize(V);
32}
33 
34void Graph::addEdge(int v, int w)
35{
36    // Add w to v’s list.
37    adj[v].push_back(w);
38}
39 
40void Graph::BFS(int s)
41{
42    // Mark all the vertices as not visited
43    vector<bool> visited;
44    visited.resize(V, false);
45 
46    // Create a queue for BFS
47    list<int> queue;
48 
49    // Mark the current node as visited and enqueue it
50    visited[s] = true;
51    queue.push_back(s);
52 
53    while (!queue.empty()) {
54         
55        // Dequeue a vertex from queue and print it
56        s = queue.front();
57        cout << s << " ";
58        queue.pop_front();
59 
60        // Get all adjacent vertices of the dequeued
61        // vertex s. If a adjacent has not been visited,
62        // then mark it visited and enqueue it
63        for (auto adjacent : adj[s]) {
64            if (!visited[adjacent]) {
65                visited[adjacent] = true;
66                queue.push_back(adjacent);
67            }
68        }
69    }
70}
71 
72// Driver code
73int main()
74{
75    // Create a graph given in the above diagram
76    Graph g(4);
77    g.addEdge(0, 1);
78    g.addEdge(0, 2);
79    g.addEdge(1, 2);
80    g.addEdge(2, 0);
81    g.addEdge(2, 3);
82    g.addEdge(3, 3);
83 
84    cout << "Following is Breadth First Traversal "
85         << "(starting from vertex 2) \n";
86    g.BFS(2);
87 
88    return 0;
89}

خروجی قطعه کد بالا را در ادامه ملاحظه می‌کنید:

Following is Breadth First Traversal (starting from vertex 2) 
2 0 3 1 

پیاده سازی الگوریتم جستجوی اول سطح با سی شارپ

در قطعه کد زیر، نحوه پیاده‌سازی الگوریتم جستجوی اول سطح را با زبان برنامه نویسی C#‎ ملاحظه می‌کنید.

1// C# program to print BFS traversal from a given source
2// vertex. BFS(int s) traverses vertices reachable from s.
3 
4using System;
5using System.Collections.Generic;
6using System.Linq;
7using System.Text;
8 
9// This class represents a directed graph
10// using adjacency list representation
11class Graph {
12 
13    // No. of vertices
14    private int _V;
15 
16    // Adjacency Lists
17    LinkedList<int>[] _adj;
18 
19    public Graph(int V)
20    {
21        _adj = new LinkedList<int>[ V ];
22        for (int i = 0; i < _adj.Length; i++) {
23            _adj[i] = new LinkedList<int>();
24        }
25        _V = V;
26    }
27 
28    // Function to add an edge into the graph
29    public void AddEdge(int v, int w)
30    {
31        _adj[v].AddLast(w);
32    }
33 
34    // Prints BFS traversal from a given source s
35    public void BFS(int s)
36    {
37 
38        // Mark all the vertices as not
39        // visited(By default set as false)
40        bool[] visited = new bool[_V];
41        for (int i = 0; i < _V; i++)
42            visited[i] = false;
43 
44        // Create a queue for BFS
45        LinkedList<int> queue = new LinkedList<int>();
46 
47        // Mark the current node as
48        // visited and enqueue it
49        visited[s] = true;
50        queue.AddLast(s);
51 
52        while (queue.Any()) {
53 
54            // Dequeue a vertex from queue
55            // and print it
56            s = queue.First();
57            Console.Write(s + " ");
58            queue.RemoveFirst();
59 
60            // Get all adjacent vertices of the
61            // dequeued vertex s. If a adjacent
62            // has not been visited, then mark it
63            // visited and enqueue it
64            LinkedList<int> list = _adj[s];
65 
66            foreach(var val in list)
67            {
68                if (!visited[val]) {
69                    visited[val] = true;
70                    queue.AddLast(val);
71                }
72            }
73        }
74    }
75 
76    // Driver code
77    static void Main(string[] args)
78    {
79        Graph g = new Graph(4);
80        g.AddEdge(0, 1);
81        g.AddEdge(0, 2);
82        g.AddEdge(1, 2);
83        g.AddEdge(2, 0);
84        g.AddEdge(2, 3);
85        g.AddEdge(3, 3);
86 
87        Console.Write("Following is Breadth First "
88                      + "Traversal(starting from "
89                      + "vertex 2) \n");
90        g.BFS(2);
91    }
92}
93 
94// This code is contributed by anv89

خروجی قطعه کد بالا را در ادامه ملاحظه می‌کنید:

Following is Breadth First Traversal (starting from vertex 2) 
2 0 3 1 

پیاده سازی الگوریتم جستجوی اول سطح با جاوا

در قطعه کد زیر، نحوه پیاده‌سازی الگوریتم جستجوی اول سطح را با زبان برنامه نویسی Java ملاحظه می‌کنید.

1// Java program to print BFS traversal from a given source
2// vertex. BFS(int s) traverses vertices reachable from s.
3 
4import java.io.*;
5import java.util.*;
6 
7// This class represents a directed graph using adjacency
8// list representation
9class Graph {
10 
11    // No. of vertices
12    private int V;
13 
14    // Adjacency Lists
15    private LinkedList<Integer> adj[];
16 
17    // Constructor
18    Graph(int v)
19    {
20        V = v;
21        adj = new LinkedList[v];
22        for (int i = 0; i < v; ++i)
23            adj[i] = new LinkedList();
24    }
25 
26    // Function to add an edge into the graph
27    void addEdge(int v, int w) { adj[v].add(w); }
28 
29    // prints BFS traversal from a given source s
30    void BFS(int s)
31    {
32        // Mark all the vertices as not visited(By default
33        // set as false)
34        boolean visited[] = new boolean[V];
35 
36        // Create a queue for BFS
37        LinkedList<Integer> queue
38            = new LinkedList<Integer>();
39 
40        // Mark the current node as visited and enqueue it
41        visited[s] = true;
42        queue.add(s);
43 
44        while (queue.size() != 0) {
45             
46            // Dequeue a vertex from queue and print it
47            s = queue.poll();
48            System.out.print(s + " ");
49 
50            // Get all adjacent vertices of the dequeued
51            // vertex s If a adjacent has not been visited,
52            // then mark it visited and enqueue it
53            Iterator<Integer> i = adj[s].listIterator();
54            while (i.hasNext()) {
55                int n = i.next();
56                if (!visited[n]) {
57                    visited[n] = true;
58                    queue.add(n);
59                }
60            }
61        }
62    }
63 
64    // Driver code
65    public static void main(String args[])
66    {
67        Graph g = new Graph(4);
68        g.addEdge(0, 1);
69        g.addEdge(0, 2);
70        g.addEdge(1, 2);
71        g.addEdge(2, 0);
72        g.addEdge(2, 3);
73        g.addEdge(3, 3);
74 
75        System.out.println(
76            "Following is Breadth First Traversal "
77            + "(starting from vertex 2)");
78 
79        g.BFS(2);
80    }
81}
82 
83// This code is contributed by Aakash Hasija

خروجی قطعه کد بالا را در ادامه ملاحظه می‌کنید:

Following is Breadth First Traversal (starting from vertex 2) 
2 0 3 1 

پیاده سازی الگوریتم جستجوی اول سطح با جاوا اسکریپت

در قطعه کد زیر، نحوه پیاده‌سازی الگوریتم جستجوی اول سطح را با زبان برنامه نویسی JavaScript ملاحظه می‌کنید.

1// Javacript Program to print BFS traversal from a given
2    // source vertex. BFS(int s) traverses vertices
3    // reachable from s.
4     
5     
6    // This class represents a directed graph using
7    // adjacency list representation
8    class Graph
9    {
10         
11        // Constructor
12        constructor(v)
13        {
14            this.V = v;
15            this.adj = new Array(v);
16            for(let i = 0; i < v; i++)
17                this.adj[i] = [];
18        }
19         
20        // Function to add an edge into the graph
21        addEdge(v, w)
22        {
23             
24            // Add w to v's list.
25            this.adj[v].push(w);
26        }
27         
28        // prints BFS traversal from a given source s
29        BFS(s)
30        {
31            // Mark all the vertices as not visited(By default
32            // set as false)
33            let visited = new Array(this.V);
34            for(let i = 0; i < this.V; i++)
35                visited[i] = false;
36             
37            // Create a queue for BFS
38            let queue=[];
39             
40            // Mark the current node as visited and enqueue it
41            visited[s]=true;
42            queue.push(s);
43             
44            while(queue.length>0)
45            {
46                // Dequeue a vertex from queue and print it
47                s = queue[0];
48                console.log(s+" ");
49                queue.shift();
50                 
51                // Get all adjacent vertices of the dequeued
52                // vertex s. If a adjacent has not been visited,
53                // then mark it visited and enqueue it
54                this.adj[s].forEach((adjacent,i) => {
55                    if(!visited[adjacent])
56                    {
57                        visited[adjacent]=true;
58                        queue.push(adjacent);
59                    }
60                });
61            }
62        }
63    }
64     
65    // Driver program to test methods of graph class
66     
67    // Create a graph given in the above diagram
68    g = new Graph(4);
69    g.addEdge(0, 1);
70    g.addEdge(0, 2);
71    g.addEdge(1, 2);
72    g.addEdge(2, 0);
73    g.addEdge(2, 3);
74    g.addEdge(3, 3);
75     
76    console.log("Following is Breadth First Traversal " +
77                "(starting from vertex 2) ");
78     
79    g.BFS(2);
80     
81    // This code is contributed by Aman Kumar.

خروجی قطعه کد بالا را در ادامه ملاحظه می‌کنید:

Following is Breadth First Traversal (starting from vertex 2) 
2 0 3 1 

پیاده سازی الگوریتم جستجوی اول سطح با پایتون

در قطعه کد زیر، نحوه پیاده‌سازی الگوریتم جستجوی اول سطح را با زبان برنامه نویسی پایتون ملاحظه می‌کنید.

1# Python3 Program to print BFS traversal
2# from a given source vertex. BFS(int s)
3# traverses vertices reachable from s.
4 
5from collections import defaultdict
6 
7 
8# This class represents a directed graph
9# using adjacency list representation
10class Graph:
11 
12    # Constructor
13    def __init__(self):
14 
15        # Default dictionary to store graph
16        self.graph = defaultdict(list)
17 
18    # Function to add an edge to graph
19    def addEdge(self, u, v):
20        self.graph[u].append(v)
21 
22    # Function to print a BFS of graph
23    def BFS(self, s):
24 
25        # Mark all the vertices as not visited
26        visited = [False] * (max(self.graph) + 1)
27 
28        # Create a queue for BFS
29        queue = []
30 
31        # Mark the source node as
32        # visited and enqueue it
33        queue.append(s)
34        visited[s] = True
35 
36        while queue:
37 
38            # Dequeue a vertex from
39            # queue and print it
40            s = queue.pop(0)
41            print(s, end=" ")
42 
43            # Get all adjacent vertices of the
44            # dequeued vertex s. If a adjacent
45            # has not been visited, then mark it
46            # visited and enqueue it
47            for i in self.graph[s]:
48                if visited[i] == False:
49                    queue.append(i)
50                    visited[i] = True
51 
52 
53# Driver code
54if __name__ == '__main__':
55 
56    # Create a graph given in
57    # the above diagram
58    g = Graph()
59    g.addEdge(0, 1)
60    g.addEdge(0, 2)
61    g.addEdge(1, 2)
62    g.addEdge(2, 0)
63    g.addEdge(2, 3)
64    g.addEdge(3, 3)
65 
66    print("Following is Breadth First Traversal"
67          " (starting from vertex 2)")
68    g.BFS(2)
69 
70# This code is contributed by Neelam Yadav

خروجی قطعه کد بالا را در ادامه ملاحظه می‌کنید:

Following is Breadth First Traversal (starting from vertex 2) 
2 0 3 1 

جمع‌بندی

یکی از اهداف ذخیره‌سازی داده‌ها در ساختمان داده‌های مختلف این است که بتوانیم در صورت نیاز، اطلاعاتی را از آن‌ها بازیابی کنیم. الگوریتم‌های جستجو بدین منظور استفاده می‌شوند و از روش‌های جستجوی مختلفی می‌توان برای استخراج اطلاعات از ساختار داده‌ها استفاده کرد.

از الگوریتم BFS‌ می‌توان به عنوان یکی از پرکاربردترین الگوریتم‌های جستجو یاد کرد که کاربردهای متنوعی در مسائل مختلف دارد. در این مطلب از مجله فرادرس سعی داشتیم به این پرسش پاسخ دهیم که الگوریتم BFS چیست و چه ویژگی‌هایی دارد. سپس، با ارائه یک مثال کاربردی، مراحل کار این الگوریتم را شرح دادیم تا درک آن برای خوانندگان ساده باشد.

بر اساس رای ۲ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
geeksforgeeksGURU99simplilearn
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *