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

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

با توجه به اینکه به هر راس حداکثر یکبار وارد میشویم در نتیجه هر یالی هم حداکثر دوبار به ازای دو سر آن شمرده می‌شود، پس در کل هزینه الگوریتم از $\mathcal{O}(n + m)$ است که $m$ تعداد یال‌ها و $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);
        }
 
    }
}

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

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

• جست‌وجو سطح‌اول - ماکزیمال
• جست‌وجو سطح‌اول - cp-algorithms
• جست‌وجو سطح‌اول - ویکی‌پدیا