DFS¶

اولین مسئله¶

فرض کنید در یک هزارتو گیر کرده اید که به صورت یک گراف است. یعنی در هر راس گراف یک اتاق قرار دارد و هر یال نشان دهنده یک راهرو بین دو اتاق است. همچنین حافظه شما به قدری قوی است که می توانید اگر به یک اتاق تکراری رفتید تشخیص بدهید که این اتاق تکراری است و هنگامی که در یک اتاق هستید تنها می توانید راهرو های مجاور آن را ببینید. همچنین یک نخ به همراه دارید که یک سر آن به اتاقی که اول کار در آن قرار دارید بسته شده است و سر دیگر در دستان شماست. در یکی از راس های گراف گنجی قرار دارد. هدف شما این است که گنج را بیابید. چگونه این کار را انجام می دهید؟

پیدا کردن گنج به سادگی انجام الگوریتم زیر است. تا زمانی که به گنج نرسیدیم الگوریتم زیر را انجام دهید :

• اگر همه اتاق های مجاور تکراری بودند به اتاقی برو که برای اولین بار از آن به اتاق فعلی آمده ای. (کافی است نخی که دستمان است را دنبال کنیم).
• در غیراینصورت به یکی از اتاق های مجاور که تکراری نیست برو.

چرا این الگوریتم مسئله ما را حل می کند؟ نکته اینجاست که زمانی که ما برای اولین بار در یک اتاق قرار می گیریم تمام تلاشمان را می کنیم که از آن اتاق مسیری به گنج پیدا کنیم. در نتیجه وقتی که همه اتاق های مجاور تکراری می شوند و ما نخ را دنبال کرده و بر می گردیم می توان نتیجه گرفت که هیچ مسیری از آن اتاق به گنج وجود ندارد. در نتیجه هیچ گاه دیگر نباید وارد این اتاق شویم. (و این منطق که نباید وارد اتاق تکراری شویم نیز از همینجا ناشی می شود).

می توان با یک دید متفاوت تر هم به مسئله نگاه کرد. به ازای هر یال \(uv\) اگر یکی از \(u,v\) را ببینیم قطعا دیگری را نیز خواهیم دید. (زیرا زمانی کارمان با یک راس تمام می شود که تمام مجاور های آن تکراری باشند). در نتیجه اگر یک راس از مولفه همبندی را ببینیم تمام راس های دیگر آن را نیز خواهیم دید.

مولفه های همبندی¶

گراف \(G\) به شما ورودی داده شده است. شما باید تعداد مولفه های همبندی این گراف را بیابید.

آنچه در این قسمت بررسی می کنیم تصویری کلی از الگوریتم dfs است. فرض کنید آرایه mark نشان می دهد که چه راس هایی قبلا دیده شده اند و در ابتدای کار تمام خانه های آن false است. حالا الگوریتم ما به اینصورت خواهد بود :

void dfs(int u){
   mark[u] = true;
   for(int y : g[u])
            if(mark[y] == false)
           dfs(y);
}

از شهودی که با حل مسئله بالا به دست آوردیم استفاده کنید. وقتی dfs(u) صدا زده می شود الگوریتم تلاش می کند که به صورت بازگشتی تمام راس هایی که با \(u\) می توان به آن رسید را ببیند سپس dfs(u) به اتمام می رسد و به راسی به نام \(par\) بر می گردیم که از آن برای اولین بار به \(u\) رسیده بودیم.

در نتیجه می توان دید که پس از اجرای این تابع تمام راس هایی که در مولفه همبندی راس شروع قرار دارند دیده می شوند. پس برای حل مسئله کافیست در هر مرحله راسی مثل \(y\) را انتخاب کنیم که mark آن false باشد. سپس dfs(y) را اجرا کرده و به جواب مسئله یکی اضافه کنیم.

درخت dfs¶

الگوریتم dfs علاوه بر اینکه گراف ما را پیمایش می کند این پیمایش را به صورت خاصی انجام می دهد! حالا با برخی از ویژگی های جالب این پیمایش آشنا می شویم.

فرض کنید یال های گراف در ابتدا آبی هستند. حالا هر گاه که برنامه در راس \(v\) بود و با طی کردن یال \(uv\) به راس جدید \(u\) می رسید یال \(uv\) را قرمز کنید.

در ابتدا توجه کنید که یال های قرمز تشکیل یک درخت می دهند! زیرا هر بار که یک یال قرمز می شود یک سر آن متصل یه راسی است که قبلا ندیده بودیم. پس مثل این است که یکی یکی به این درخت برگ اضافه می کنیم! به این درخت به دست آمده از الگوریتم dfs، درخت dfs می گوییم. ویژگی جالب dfs این است که وقتی اجرای dfs(u) شروع می شود راس \(u\) در درخت قرمز ها تنها یک برگ است و زمانی که اجرای dfs(u) به پایان می رسد زیردرخت \(u\) به طور کامل ساخته شده است. پس می بینید که پس از اجرای الگوریتم dfs روی یک گراف همبند، یک درخت فراگیر از این گراف را به دست خواهیم آورد. این درخت فراگیر را از راس شروع ریشه دار کنید.

حالا به ویژگی جالبی که روی یال های آبی به دست می آید توجه کنید.

به یال \(uv\) بک اج (back edge) می گوییم اگر یکی از \(u,v\) جد دیگری باشد. در غیراینصورت به این یال کراس اج (cross edge) می گوییم. البته ممکن است بعضا یک دسته تری ادج (tree edge) در نظر بگیرند و یال های خود درخت را تری ادج و یال های دیگر را بک ادج در نظر بگیرند اما ما در اینجا همه را بک ادج در نظر می گیریم و به این دو دسته اکتفا می کنیم.

ادعا می کنیم برای هر درخت dfs تمام یال های گراف بک اج هستند!

برای اثبات اینکه تمام یال ها بعد از پیمایش dfs بک اج هستند یک یال \(uv\) دلخواه را در نظر بگیرید. بدون کم شدن از کلیت مسئله فرض کنید در الگوریتم ابتدا به راس \(u\) وارد شده ایم. در اینصورت موقع شروع dfs(u) راس \(v\) هنوز دیده نشده است. همچنین زمانی که dfs(u) به پایان می رسد راس \(v\) باید دیده شده باشد (زیرا مجاور راس \(u\) است). بنابراین اگر درخت dfs را در نظر بگیرید راس \(v\) باید درون زیردرخت \(u\) باشد! در نتیجه \(u\) جد \(v\) است پس یال \(uv\) بک اج خواهد بود.

در آینده از این قضیه که بعد از اجرای dfs تمام یال ها بک اج هستند استفاده های بسیاری خواهیم کرد!

مسیر ماکسیمال و dfs¶

در فصل 1 با اثبات هایی که توسط مسیر ماکسیمال انجام می شد آشنا شدیم. در اینجا یاد می گیریم که می توان به جای استفاده از مسیر ماکسیمال از برگ های درخت dfs استفاده کرد(که شهود بسیار قوی تری ایجاد می کند)!

بعد از dfs زدن روی درخت، تعداد بک اج هایی که \(u\) راس پایین آن است را \(back_u\) می نامیم. توجه کنید که یال های درخت dfs هم طبق تعریف ما بک اج محسوب می شوند. همچنین ارتفاع راس \(u\) در درخت را \(h_u\) می نامیم.

دو قضیه زیر به راحتی از ساختار خاص درخت نتیجه می شوند (قضیه دوم با فرض ساده بودن گراف برقرار است).

• \(\sum back_u = m\)
• \(\forall_u back_u \leq h_u\)

پیمایش درخت¶

یکی از حالات خاص مسئله پیمایش گراف، پیمایش درخت ها است. در این قسمت می بینیم که پیمایش درخت ها می تواند با الگوریتم dfs به صورت ساده تر انجام شود. مثلا دیگر به آرایه mark نیازی نداریم. زیرا تنها مجاور یک راس که قبلا دیده شده است پدر این راس می باشد.

همچنین می توان همزمان به اجرای dfs اطلاعات دیگری نیز درباره درخت به دست آورد. به عنوان مثال در کد زیر بعد از اجرای dfs روی درخت تعداد راس های زیردرخت هر راس در آرایه sz، و ارتفاع هر راس در آرایه h ذخیره سازی می شوند.

توجه کنید که فرض کردیم اندیس راس های درخت از 1 شروع می شوند و راس با اندیس 0 نداریم.

const int maxn = 1e5 + 10;

vector <int> g[maxn];
int sz[maxn], h[maxn];

void dfs(int u, int par = 0){
   h[u] = h[par] + 1;
   sz[u] = 1;
   for(int y : g[u]){
       if(y != par){
           dfs(y, u);
           sz[u] += sz[y];
       }
   }
}