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

جست‌و‌جوی اول‌سطح (‌Breadth First Search) که به bfs مشهور است، روشی برای پیمایش گراف است که بعد از جست‌وجوی عمق‌اول مهم‌ترین و پرکاربرد‌ترین الگوریتم پیمایش گراف است. این الگوریتم معمولا در گراف‌ها‌ی وزن دار کاربرد خاصی ندارد و عمده نقش آن در گراف‌های بی‌وزن و برای پیدا کردن کوتاه‌ترین فاصله بین یک راس تا بقیه‌ی راس‌هااست.

این الگوریتم ابتدا یک راس ریشه مانند v را به عنوان شروع میگیرد. سپس راس‌ها را سطح بندی میکند. سطح بندی به این صورت است که تمام راس‌های مجاور v را در سطح اول قرار میدهیم، حال برای سطح $i+1$، راس u که مجاور یکی از رئوس سطح $i$ است را در این سطح قرار میدهیم به شرطی که u در هیچ سطح دیگری نیامده باشد. به عبارت دیگر راس هارا بر اساس کوتاه‌ترین فاصله از v سطح بندی میکنیم. حال برای پیمایش به ترتیب سطح، و در هر سطح به ترتیب دلخواه وارد راس‌ها میشویم. پس اولین زمانی که به هر راس می‌رسیم، با کمترین فاصله ممکن نسبت به v رسیده ایم.

با توجه به اینکه به هر راس حداکثر یکبار وارد میشویم در نتیجه هر یالی هم حداکثر دوبار به ازای دو سر آن شمرده می‌شود، پس در کل هزینه الگوریتم از $O(n + e)$ است که e تعداد یال‌ها و n تعداد راس‌ها است.

برای ایجاد سطح های مختلف و حرکت به ترتیب سطح ها نیاز به استفاده از صف داریم.
فرض کرده ایم که لیست مجاورت راس ها را داده اند و الگوریتم راس آغازین را نیز از ورودی می‌گیرد.

bfs.cpp

#include <queue>
#include <vector>
 
const int MAXN = 100 * 1000 + 10;
 
bool mark[MAXN];
int vector<int> adj[MAXN];
 
void bfs(int v) {
    queue<int> q;
 
    mark[v] = 1;
    q.push(v);
 
    while(q.size()) {
        v = q.front(); //    راس ابتدایی را از صف بر میداریم
        q.pop();
        // کار‌ها‌ی پیش‌ترتیب را اینجا مینویسیم
        for(int i = 0; i < adj[v].size(); i++) {
            int u = adj[v][i];
 
            if (mark[u] == 1) //    قبلا این راس را به صف اضافه نکرده باشیم
                continue;
 
            mark[u] = 1;
            q.push(u);
        }
 
    }
}

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

• تابع اویلر - سایت ماکزیمال
• تابع اویلر - ویکی‌پدیا