You are not allowed to perform this action

جست‌و‌جوی عمق‌اول

تعریف

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

الگوریتم

الگوریتم به این شکل است که ابتدا یک رأس مانند $v$ را انتخاب می‌کنیم و آن را ریشه می‌نامیم. ریشه را علامت‌گذاری می‌کنیم. سپس یک رأس دل خواه علامت نخورده‌ی مجاور با $v$ را انتخاب می‌کنیم و آن را $u$ می‌نامیم. $u$ را یکی از بچه‌های $v$ می‌کنیم، سپس $u$ را علامت می‌زنیم. حال همین الگوریتم را روی $u$ از ابتدا اجرا می‌کنیم (یعنی یکی از همسایه‌های مجاور و علامت نخورده $u$ را انتخاب می‌کنیم و …).

الگوریتم گفته شده زمانی به بن‌بست می‌خورد که به ازای راسی مانند $u$، تمام همسایه‌هایش علامت خورده باشند. در این صورت به راس پدر (رأسی که از آن وارد $u$ شدیم) بر‌می‌گردیم و دوباره همین الگوریتم را از ادامه اجرا می‌کنیم (یعنی وارد پدر $u$ می‌شویم و اگر همسایه‌ی علامت نخورده‌ای داشت وارد آن می‌شویم و اگر نداشت به رأس پدرش باز می‌گردیم). برنامه زمانی متوقف می‌شود که به رأس $v$ برگشته باشیم و تمام همسایه‌هایش علامت خورده باشند که در این صورت می‌گوییم الگوریتم پایان یافته است. دقت کنید که اگر گراف شما همبند نباشد، این جست‌و‌جو تنها رأس‌های مؤلفه ریشه را پیمایش می‌کند پس برای پیمایش روی تمام رأس‌ها این الگوریتم را به ازای هر رأس علامت‌نخورده‌ای تکرار می‌کنیم.

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

ویژگی‌ها

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

مجموع این ویژگی‌ها باعث شده که این الگوریتم تبدیل به الگوریتمی مهم و کاربردی شود.

پیچیدگی‌ الگوریتم

از آنجایی که هر رأس حداکثر یک بار پیمایش می‌شود و در پیمایش یک راس از مرتبه درجه آن راس عملیات انجام می‌شود پس این الگوریتم پیچیدگی زمانی از مرتبه $\mathcal{O}(n+m)$ دارد. که $n$ تعداد رأس‌ها و $m$ تعداد یال‌ها است.

پیاده‌سازی

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

dfs.cpp
#include <vector>
#include <iostream>
 
const int MAXN = 100 * 1000 + 10;
 
using namespace std;
 
bool mark[MAXN];
int color[MAXN];  // رنگ رأس
int start[MAXN];  // زمان شروع
int finish[MAXN];  // زمان پایان
vector <int> adj[MAXN];  // لیست مجاورت
int n;   // تعداد رأس‌ها
int m;   // تعداد یال‌ها
int now_time;  // زمان فعلی
 
void dfs(int v) {
    mark[v] = 1;
    color[v] = 1;        // این رأس را خاکستری کن
    start[v] = now_time++;
    // کارهای پیش‌ترتیب را انجام بده
    for(int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if(mark[u] != 1)
            dfs(u);
 
        // کار‌های پس‌ترتیب این یال را انجام بده
    }
    color[v] = 2;        // این رأس را سیاه کن
    finish[v] = now_time;  // می‌توانید هنگام خروج هم زمان را اضافه کنید.
    // کار‌های پس‌ترتیب این رأس را انجام بده
}
 
 
void input()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        adj[--v].push_back(--u);
        adj[u].push_back(v);
    }
}
 
int main()
{
    input();
    for (int i = 0; i < n; i++)
        if(mark[i] == 0)
            dfs(i);
}

مراجع