DFS
=========

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

اولین مسئله
-------------

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

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

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

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

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

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

گراف :math:`G` به شما ورودی داده شده است. شما باید تعداد مولفه های همبندی این گراف را بیابید.

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

.. code-block:: cpp

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

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

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


درخت dfs
-----------------

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

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

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

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

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


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

.. figure:: /_static/dot/Back_Edge.svg
   :width: 50%
   :align: center
   :alt: اگه اینترنت یارو آشغال باشه این میاد


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

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

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

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

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

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

- :math:`\sum back_u = m`
- :math:`\forall_u back_u \leq h_u`
مسیر به طول :math:`\delta`
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ثابت می کنیم که یک گراف ساده مسیری به طول حداقل :math:`\delta` دارد. کافیست ثابت کنیم ارتفاع درخت dfs حداقل :math:`\delta` است. یک برگ دلخواه مثل :math:`u` را در نظر بگیرید. واضح است که :math:`back_u \geq \delta` در نتیجه :math:`h_u \geq \delta` که حکم ما را به سادگی نتیجه می دهد!

مسیر به طول :math:`\frac m n`
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ثابت می کنیم که یک گراف ساده مسیری به طول حداقل :math:`\frac m n` دارد. مثل بالا ثابت می کنیم ارتفاع درخت dfs حداقل :math:`\frac m n` است. برای اثبات از برهان خلف استفاده می کنیم. فرض کنید ارتفاع هر راس کمتر از :math:`\frac m n` باشد. داریم :
:math:`m = \sum back_u \leq \sum h_u < n \times \frac m n = m \Rightarrow m < m`

که به ما تناقض می دهد. در نتیجه راسی با ارتفاع حداقل :math:`\frac m n` وجود دارد که حکم مسئله ما را ثابت می کند.

برگ ها و ارتفاع، مجموعه مستقل و طولانی ترین مسیر!
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

فرض کنید بعد از اعمال الگوریتم dfs ارتفاع درخت برابر با :math:`H` شود(در واقع :math:`H` بیشینه مقدار بین :math:`h_u` ها است). همچنین فرض کنید تعداد برگ ها :math:`S` باشد.

در اینجا ثابت می کنیم که :math:`H \times S \geq n-1`.

به ازای هر برگ درخت مسیر این راس تا ریشه را طی کنید و روی هر راس این مسیر به جز ریشه یک سنگ قرار دهید. در اینصورت به ازای هر برگ مثل :math:`u` به تعداد کل سنگ ها :math:`h_u` تا اضافه می شود. از طرفی روی هر راس به جز ریشه حداقل یک سنگ قرار دادیم در نتیجه تعداد کل سنگ ها حداقل :math:`n-1` می باشد. پس می توان نوشت :

:math:`n-1 \leq \sum h_u \leq H \times S`

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

در نتیجه اگر اندازه مجموعه مستقل بیشینه :math:`S^{\prime}` باشد در اینصورت :math:`S \leq S^{\prime}` برقرار است.

همینطور اگر اندازه طولانی ترین مسیر این گراف :math:`H^{\prime}` باشد در اینصورت :math:`H \leq H^{\prime}` برقرار است.

پس حالا توانستیم به نامساوی جالب :math:`n-1 \leq H \times S \leq H^{\prime} \times S^{\prime}` برسیم!

نکته جالب این است که هر دو مسئله پیدا کردن مچموعه مستقل با بیشترین بیشینه و طولانی ترین مسیر در گراف np هستند! اما با روشی که ارائه دادیم می توانیم یا یک مجموعه مستقل به اندازه حداقل :math:`\sqrt{n-1}` یا یک مسیر به اندازه حداقل :math:`\sqrt{n-1}` ارائه دهیم!

راس نابرشی
~~~~~~~~~~~~~~~~

ثابت می کنیم هر گراف با :math:`n > 1` حداقل دو راس نابرشی دارد.

کافیست روی گراف dfs بزنید. سپس هر کدام از برگ های درخت dfs یک راس نابرشی خواهند بود (همچنین اگر این دو راس را با هم نیز حذف کنیم گراف ناهمبند نمی شود). زیرا که یال های درخت dfs بقیه گراف را همبند نگه می دارد (و حذف برگ از یک درخت همبندی آن را خراب نمی کند). همچنین هر درخت با :math:`n>1` حداقل دو برگ دارد که حکم ما را ثابت می کند. البته در این مسئله نیازی به استفاده از درخت dfs نبود و هر درخت فراگیر دلخواهی مسئله را برای ما حل می کرد.

پیمایش درخت
--------------------

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

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

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

.. code-block:: cpp
  
  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];
         }
     }
  }