خانه ویکی

جست و جوی عمق اول (Depth First Serach)

DFS یکی دیگر از الگوریتم های پر کاربرد در پیمایش گراف است. DFS اولین مسیر lexicographical از ریشه (v) به هر راس دیگری در گراف را پیدا میکند.(اگر رئوس در گراف با یک یا چند حرف نامگذاری شده باشند ، آنگاه مسیر lexicographical ، مسیری است که رئوس به ترتیب دیکشنری طی شوند). همچنین DFS کوتاه ترین مسیر در درخت را نیز پیدا می کند ؛ برای اینکه در درخت فقط یک مسیر به هر راس وجود دارد ولی در گراف های دیگر از DFS به عنوان الگوریتمی برای یافتن کوتاه ترین مسیر استفاده نمی کنند. اردر این الگوریتم از (O(n+m است که n تعداد رئوس و m تعداد یال ها است.

توضیح الگوریتم

در واقع ایده های که در پشت DFS نهفته است این است که تا جایی که می توان در عمق گراف پیش رفت و وقتی به یک راس رسیدیم که هیچ همسایه دیده نشده ایی نداشت، به عقب بر می گردیم. الگوریتم به این شکل است که ابتدا ریشه (v) را انتخاب می کنیم و mark[v]=true می کنیم. سپس به یکی از همسایه های v مانند u که mark[u]=false است می رویم و همین الگوریتم را روی u و دیگر رئوس اجرا می کنیم. زمانی که به ازای راسی مانند u، تمام همسایه هایش را دیدیم به راس پدر ( راسس که از آن وارد u شده بودیم ) بر می گردیم و دوباره همین الگوریتم را اجرا می کنیم. برنامه زمانی تمام می شود که به راس ریشه (v) برگشته باشیم و به ازای هر همسایه v مانند mark[a]=true ، a باشد.

کاربرد ها

طبقه بندی یال ها در گراف

ما می توانیم یال های یک گراف را با توجه به starting time و finishing time دو سر یال (u,v) طبقه بندی کنیم. این طبقه بندی ها معمولا در حل کردن مسائلی چون پیدا کردن پل ها(Bridges) و یافتن راس های برشی استفاده می شود. در ابتدا DFS را روی گراف اجرا کرده و سپس یال هایی که با آن ها مواجه شدیم را این طور طبقه بندی می کنیم :

پیاده سازی

vector<vector<int>> adj; // graph represented as an adjacency list
int n; // number of vertices

vector<bool> visited;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u])
            dfs(u);
    }
}

این ساده ترین دی اف اس ممکن است. همان طور که در کاربرد ها صحبت کردیم، ممکن است محاسبه starting time یا چیز های دیگر مفید باشد. این پیاده سازی دی اف اس با محاسبه ی مقادیر کاربردی در بخش کاربرد هاست.

vector<vector<int>> adj; // graph represented as an adjacency list
int n; // number of vertices

vector<int> color;

vector<int> time_in, time_out;
int dfs_timer = 0;

void dfs(int v) {
    time_in[v] = dfs_timer++;
    color[v] = 1;
    for (int u : adj[v])
        if (color[u] == 0)
            dfs(u);
    color[v] = 2;
    time_out[v] = dfs_timer;
}

مسائل تمرینی