الگوریتم 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 به ترتیب تعداد فرزندان هر گره و عمق درخت را نشان می‌دهند.

فیلم آموزش مروری بر پیچیدگی محاسبات Computational Complexity در تم آف

کلیک کنید

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

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

فیلم آموزش طراحی الگوریتم در تم آف

کلیک کنید

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

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

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

فیلم آموزش ساختمان داده ها – مرور و تست کنکور ارشد در تم آف

کلیک کنید

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

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

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

فیلم مجموعه آموزش ساختمان داده و طراحی الگوریتم در تم آف

کلیک کنید

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

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

#include 
#include 
#include 
 
#define MAX_VERTICES 50
 
// This struct represents a directed graph using
// adjacency list representation
typedef struct Graph_t {
     
    // No. of vertices
    int V;
    bool adj[MAX_VERTICES][MAX_VERTICES];
} Graph;
 
// Constructor
Graph* Graph_create(int V)
{
    Graph* g = malloc(sizeof(Graph));
    g->V = V;
 
    for (int i = 0; i adj[i][j] = false;
        }
    }
 
    return g;
}
 
// Destructor
void Graph_destroy(Graph* g) {
    free(g);
}
 
// function to add an edge to graph
void Graph_addEdge(Graph* g, int v, int w)
{
    // Add w to v’s list.
    g->adj[v][w] = true;
}
 
// Prints BFS traversal from a given source s
void Graph_BFS(Graph* g, int s)
{
    // Mark all the vertices as not visited
    bool visited[MAX_VERTICES];
    for (int i = 0; i V; i++) {
        visited[i] = false;
    }
 
    // Create a queue for BFS
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;
 
    // Mark the current node as visited and enqueue it
    visited[s] = true;
    queue[rear++] = s;
 
    while (front != rear) {
        // Dequeue a vertex from queue and print it
        s = queue[front++];
        printf("%d ", s);
 
        // Get all adjacent vertices of the dequeued
        // vertex s. If a adjacent has not been visited,
        // then mark it visited and enqueue it
        for (int adjacent = 0; adjacent V;
             adjacent++) {
            if (g->adj[s][adjacent] && !visited[adjacent]) {
                visited[adjacent] = true;
                queue[rear++] = adjacent;
            }
        }
    }
}
 
// Driver code
int main()
{
    // Create a graph
    Graph* g = Graph_create(4);
    Graph_addEdge(g, 0, 1);
    Graph_addEdge(g, 0, 2);
    Graph_addEdge(g, 1, 2);
    Graph_addEdge(g, 2, 0);
    Graph_addEdge(g, 2, 3);
    Graph_addEdge(g, 3, 3);
 
    printf("Following is Breadth First Traversal "
           "(starting from vertex 2) n");
    Graph_BFS(g, 2);
    Graph_destroy(g);
 
    return 0;
}

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

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

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

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

// C++ code to print BFS traversal from a given
// source vertex
 
#include 
using namespace std;
 
// This class represents a directed graph using
// adjacency list representation
class Graph {
 
    // No. of vertices
    int V;
 
    // Pointer to an array containing adjacency lists
    vector > adj;
 
public:
    // Constructor
    Graph(int V);
 
    // Function to add an edge to graph
    void addEdge(int v, int w);
 
    // Prints BFS traversal from a given source s
    void BFS(int s);
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj.resize(V);
}
 
void Graph::addEdge(int v, int w)
{
    // Add w to v’s list.
    adj[v].push_back(w);
}
 
void Graph::BFS(int s)
{
    // Mark all the vertices as not visited
    vector visited;
    visited.resize(V, false);
 
    // Create a queue for BFS
    list queue;
 
    // Mark the current node as visited and enqueue it
    visited[s] = true;
    queue.push_back(s);
 
    while (!queue.empty()) {
         
        // Dequeue a vertex from queue and print it
        s = queue.front();
        cout 

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

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

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

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

// C# program to print BFS traversal from a given source
// vertex. BFS(int s) traverses vertices reachable from s.
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
// This class represents a directed graph
// using adjacency list representation
class Graph {
 
    // No. of vertices
    private int _V;
 
    // Adjacency Lists
    LinkedList[] _adj;
 
    public Graph(int V)
    {
        _adj = new LinkedList[ V ];
        for (int i = 0; i ();
        }
        _V = V;
    }
 
    // Function to add an edge into the graph
    public void AddEdge(int v, int w)
    {
        _adj[v].AddLast(w);
    }
 
    // Prints BFS traversal from a given source s
    public void BFS(int s)
    {
 
        // Mark all the vertices as not
        // visited(By default set as false)
        bool[] visited = new bool[_V];
        for (int i = 0; i  queue = new LinkedList();
 
        // Mark the current node as
        // visited and enqueue it
        visited[s] = true;
        queue.AddLast(s);
 
        while (queue.Any()) {
 
            // Dequeue a vertex from queue
            // and print it
            s = queue.First();
            Console.Write(s + " ");
            queue.RemoveFirst();
 
            // Get all adjacent vertices of the
            // dequeued vertex s. If a adjacent
            // has not been visited, then mark it
            // visited and enqueue it
            LinkedList list = _adj[s];
 
            foreach(var val in list)
            {
                if (!visited[val]) {
                    visited[val] = true;
                    queue.AddLast(val);
                }
            }
        }
    }
 
    // Driver code
    static void Main(string[] args)
    {
        Graph g = new Graph(4);
        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 2);
        g.AddEdge(2, 0);
        g.AddEdge(2, 3);
        g.AddEdge(3, 3);
 
        Console.Write("Following is Breadth First "
                      + "Traversal(starting from "
                      + "vertex 2) n");
        g.BFS(2);
    }
}
 
// This code is contributed by anv89

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

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

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

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

// Java program to print BFS traversal from a given source
// vertex. BFS(int s) traverses vertices reachable from s.
 
import java.io.*;
import java.util.*;
 
// This class represents a directed graph using adjacency
// list representation
class Graph {
 
    // No. of vertices
    private int V;
 
    // Adjacency Lists
    private LinkedList adj[];
 
    // Constructor
    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i  queue
            = new LinkedList();
 
        // Mark the current node as visited and enqueue it
        visited[s] = true;
        queue.add(s);
 
        while (queue.size() != 0) {
             
            // Dequeue a vertex from queue and print it
            s = queue.poll();
            System.out.print(s + " ");
 
            // Get all adjacent vertices of the dequeued
            // vertex s If a adjacent has not been visited,
            // then mark it visited and enqueue it
            Iterator i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
 
    // Driver code
    public static void main(String args[])
    {
        Graph g = new Graph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
 
        System.out.println(
            "Following is Breadth First Traversal "
            + "(starting from vertex 2)");
 
        g.BFS(2);
    }
}
 
// This code is contributed by Aakash Hasija

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

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

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

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

// Javacript Program to print BFS traversal from a given
    // source vertex. BFS(int s) traverses vertices
    // reachable from s.
     
     
    // This class represents a directed graph using
    // adjacency list representation
    class Graph
    {
         
        // Constructor
        constructor(v)
        {
            this.V = v;
            this.adj = new Array(v);
            for(let i = 0; i 0)
            {
                // Dequeue a vertex from queue and print it
                s = queue[0];
                console.log(s+" ");
                queue.shift();
                 
                // Get all adjacent vertices of the dequeued
                // vertex s. If a adjacent has not been visited,
                // then mark it visited and enqueue it
                this.adj[s].forEach((adjacent,i) => {
                    if(!visited[adjacent])
                    {
                        visited[adjacent]=true;
                        queue.push(adjacent);
                    }
                });
            }
        }
    }
     
    // Driver program to test methods of graph class
     
    // Create a graph given in the above diagram
    g = new Graph(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
     
    console.log("Following is Breadth First Traversal " +
                "(starting from vertex 2) ");
     
    g.BFS(2);
     
    // This code is contributed by Aman Kumar.

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

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

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

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

# Python3 Program to print BFS traversal
# from a given source vertex. BFS(int s)
# traverses vertices reachable from s.
 
from collections import defaultdict
 
 
# This class represents a directed graph
# using adjacency list representation
class Graph:
 
    # Constructor
    def __init__(self):
 
        # Default dictionary to store graph
        self.graph = defaultdict(list)
 
    # Function to add an edge to graph
    def addEdge(self, u, v):
        self.graph[u].append(v)
 
    # Function to print a BFS of graph
    def BFS(self, s):
 
        # Mark all the vertices as not visited
        visited = [False] * (max(self.graph) + 1)
 
        # Create a queue for BFS
        queue = []
 
        # Mark the source node as
        # visited and enqueue it
        queue.append(s)
        visited[s] = True
 
        while queue:
 
            # Dequeue a vertex from
            # queue and print it
            s = queue.pop(0)
            print(s, end=" ")
 
            # Get all adjacent vertices of the
            # dequeued vertex s. If a adjacent
            # has not been visited, then mark it
            # visited and enqueue it
            for i in self.graph[s]:
                if visited[i] == False:
                    queue.append(i)
                    visited[i] = True
 
 
# Driver code
if __name__ == '__main__':
 
    # Create a graph given in
    # the above diagram
    g = Graph()
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(1, 2)
    g.addEdge(2, 0)
    g.addEdge(2, 3)
    g.addEdge(3, 3)
 
    print("Following is Breadth First Traversal"
          " (starting from vertex 2)")
    g.BFS(2)
 
# This code is contributed by Neelam Yadav

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

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

جمع‌بندی

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

فیلم مجموعه آموزش ساختمان داده و طراحی الگوریتم در تم آف

کلیک کنید

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