BFS
=============
در این بخش به معرفی الگوریتم bfs که یک راه برای پیمایش گراف است و همچنین خاصیت های آن میپردازیم.

الگوریتم bfs 
----------

ابتدا یک راس را مشخص میکنیم (نام ان را root میگزاریم) و آن را در گروه :math:`A_0` میگزاریم سپس تمام همسایه های ان را در گروه :math:`A_1` میگزاریم و
در :math:`A_2` تمام همسایه های گروه های :math:`A_0` و :math:`A_1` را میگزاریم که تا الان در هیچ گروهی نیامد اند و به همین شکل در گروه :math:`A_i` تمام 
راس هایی که همسایه راس های گروه های :math:`A_j` که :math:`0 \leqslant j < i` است و در آن ها  نیامده قرار میدهیم.

فرض کنید :math:`Dis_i` برابر شماره گروهی است که :math:`i` در آن امده است(برای مثال :math:`Dis_{root} = 0` است).
واضح است در این روش تمام راس هایی که در مولفه همبندی root است در گروه ها می ایند پس برای راحتی کار فرض میکنیم گراف همبند است ولی هر چه میگوییم در واقع برای مولفه همبندی root درست است.

ابتدا ثابت میکنیم برای دو راس :math:`i,j` که به هم یال دارند :math:`1`  :math:`\leqslant`  :math:`|Dis_{i}-Dis_{j}|`.

اثبات:برهان خلف میزنیم،فرض کنید دو راس :math:`i,j` است که همسایه هم هستند و :math:`Dis_{j} - Dis_{i} > 1`. حال زمانی را در نظر بگیرید که داشتیم گروه 
:math:`A_{Dis_{i}+1}` را  پر میکردیم ، آن لحظه :math:`j` در هیچ گروهی نیامده بود و همسایه :math:`i` بود پس در گروه :math:`A_{Dis_{i}+1}` 
بود و با تناقض بدست امده قضیه ثابت شد.
پس میتوانیم فرض کنیم در گروه :math:`A_i` تمام 
راس هایی که همسایه راس های گروه های :math:`A_{i-1}` و در آن نیامده قرار میدهیم.

.. figure:: /_static/dot/BFS_Groups.svg
   :width: 100%
   :align: left
   :alt: اگه اینترنت یارو آشغال باشه این میاد
.. figure:: /_static/dot/BFS_Graph.svg
   :width: 100%
   :align: right
   :alt: اگه اینترنت یارو آشغال باشه این میاد

|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|

حال ثابت میکنیم :math:`Dis_{i}` = :math:`dis(i,root)`.

اثبات:برهان خلف میزنیم ، راسی که کمترین مقدار Dis را دارد و حکم ما برای آن برقرار نیست(نام آن را i میگزاریم)
حال همسایه i را در مسیری به root که تعداد یال های آن مسیر برابر :math:`dis(root,i)` است در نظر بگیرید.(با نام j)
چون راس i کمترین Dis را بین راس هایی که حکم را نقض میکردند داشت پس j حکم را نقض نمیکرد پس:

- :math:`Dis_{j}=dis(root,i)-1`
-  و چون :math:`Dis_{i} > Dis_{j}` و :math:`1` :math:`\leqslant` :math:`|Dis_{i}-Dis_{j}|` پس:
- :math:`Dis_{i} = Dis_{j}+1`

و با تناقض بدست امده قضیه اثبات شد.

حال الگوریتم را کمی تغییر میدهیم و ثابت میکنیم باز همان کار را داریم انجام میدهیم :

یک گروه جدید میسازیم با نام B که ابتدا راس root را در آن میگزاریم و سپس تا زمانی که B تهی نشده کار زیر را انجام میدهیم:

راسی در B که کمترین مقدار Dis را دارد در نظر میگیریم(با نام i) i را از B حذف میکنیم سپس تمام همسایه های آن را که هنوز در هیچ A ای نبود را در گروه :math:`A_{Dis_i} + 1` میگزاریم و آن را داخل B میگزاریم.
این الگوریتم نیز مانند الگوریتم بالایی است فقط بجای آن که همه راس های :math:`A_i` با هم در نظر بگیریم و همه همسایه های آن ها که تا بحال در گروهی نیامده در گروه بعدی بگزاریم
, روی راس های داخل گروه :math:`A_i` را با ترتیبی که فرقی ندارد چه گونه است حرکت میکنیم و هر راس از گروه بعد در اولین زمانی که یک همسایه از آن در :math:`A_i` را
دیدیم وارد :math:`A_{i+1}` میشود.
واضح است وقتی یک راس وارد B میشود مقدار Dis آن از بقیه راس های داخل B بیشتر است پس اگر راس های داخل B را به ترتیب ورودشان در B نگه داریم عملا هر دفعه راس ته B را میگیریم آن را حذف میکنیم و راس های همسایه آن را که تابحال در B نیامده ان به سر اضافه میکنیم.

درخت bfs
---------

زمانی که الگوریتم bfs  به پایان میرسد را در نظر بگیرید(یعنی زمانی که هر راس مشخص شد در کدام گروه است). حال برای راس i ما :math:`par_i` را به دلخواه یکی از همسایه های i مانند j به طوری که 
:math:`Dis_{i} = Dis_{j}+1` است در نظر میگیریم(واضح است par برای root تعریف نمیشود و برای هر راس دیگر هم قطعا تعریف میشود).سپس برای هر راس به غیر از root یال بین i و :math:`par_i` را نگه میداریم و بقیه یال ها را حذف میکنیم. تعداد یال های باقی مانده n-1 است و هر راس نیز به root مسیر دارد(چرا؟). پس گراف جدید ما همبند است در نتیجه درخت است.

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

در واقع درخت
bfs
را میتوان یک زیر درخت فراگیر در گراف در نظر گرفت که از
root
اویزان شده و دارای دو ویژگی زیر است :

- برای هر راس مانند i :math:`dis(root,i) = h_i` (:math:`h_i` ارتفاع راس i وقتی که درخت را از root اویزان کردیم است).
- برای هر یال در **گراف اصلی** اختلاف ارتفاع دو سر آن حداکثر یک است.

علاوه از استفاده هایی که در برنامه نویسی از درخت bfs میشود و ممکن است در سوالی به درد شما بخورد درخت bfs در حل برخی مسائل تئوری نیز میتواند راه گشا باشد که در دو مثال زیر آن را نشان میدهیم.

|
|
|
|
|
|
|

قضیه
~~~~~~

صورت قضیه :

کد bfs
------

نحوه ورودی : ابتدا دو عدد n , m به ما داده میشود که به ترتیب بیانگر تعداد راس ها و تعداد یال های گراف است سپس در m خط بعدی دو عدد i , j میدهند
که نشان میدهد بین i , j در گراف یال وجود دارد.

باید n عدد چاپ کنیم که عدد i برابر :math:`dis(1,i)` است . تضمین شده گراف همبند است تا فاصله هر راس از 1 عددی حسابی باشد .
 
راه حل :

ما از queue که یک صف است در کد استفاده میکنیم queue دارای قابلیت های زیادی است ولی قابلیت های مورد استفاده ما در زیر امده :

- :math:`queue<int>q`
- :math:`q.size( )` برابر تعداد عناصر داخل q است.
- :math:`q.front( )` مقدار عنصر ته  q
- :math:`q.pop( )` حذف عنصر ته q
- :math:`q.push(x)` اضافه کردن x به q از سر آن
- queue در واقع برای ما نقش گروه B را ایفا میکند.

همچنین از ارایه Mark استفاده میکنیم که مقدار اولیه آن برای هر راس صفر است و اگه راسی وارد B  شود مقدار آن برای آن راس 1 میشود.
و از ارایه Dis هم استفاده میکنیم که برای هر راس جواب در آن ذخیره میشود.

.. code-block:: cpp

  const int maxn = 1e5 + 10;// hadeaksar meghdare n
  int n, m;// tedad ras ha va tedad yal ha
  int Dis[maxn];//javab har ras
  bool Mark[maxn];//neshan midahad aya yek ras tabehal varede queue shode ya na
  queue <int> q;// toozihe un neveshte shode
  vector<int> adj[maxn] ;//list hamsaye haye har ras dar un neveshte shode
  
  void bfs(int root){//fasele harki az root bedast khahad amad
      Dis[root] = 0; // dis(root , root) = 0
      Mark[root] = 1;
      q.push(root); 
      while(q.size()){//ta zamani ke dakhele q ras hast while ra edame bede
          int u = q.front();//rasi dar q ke kamtarin Dis ra darad
          q.pop(); //hazfe un
          for(int i = 0; i < adj[u].size(); i++){//hamsaye haye i ra negah mikonim va agar ta be hal vared q nashodan vared mikonim
              int v = adj[u][i];
                if(!Mark[v]){
                    Mark[v] = 1;
                    Dis[v] = Dis[u] + 1;
                    q.push(v);
                }
          }
      }
  }
  
  int main(){
      cin >> n >> m ;
      for(int i = 1; i <= m; i++){//list hamsaye haye ras ha ra por mikonim
          int u, v;
          cin >> u >> v ;
          adj[u].push_back(v);
          adj[v].push_back(u);
      }
      bfs(1);//yani be ezaye root = 1 tabe bfs ra seda bezan
      for(int i = 1; i <= n; i++)//chupe khrooji
         cout << Dis[i] << ' ';
  }

در این الگوریتم هر راس حداکثر یک بار وارد q میشود و هر یال هم به ازای هر سر حداکثر یک بار صدا میشود پس الگوریتم ما از :math:`O(n+m)` است.

نتیجه گیری
--------

در این بخش به معرفی الگوریتم bfs و ویژگی های آن پرداختیم . از مهمترین کاربرد های های bfs میتولن به موارد زیر اشاره کرد.

- پیدا کردن فاصله هر راس از راسی خاص
- پیدا کردن راس های داخل مولفه همبندی راسی خاص(در نتیجه تشخیص همبند بودن یا نبودن گراف)
- پیمایش گراف به منظوری خاص
- استفاده از مفهوم bfs و bfs tree در حل سوالات تئوری

توصیه میشود حتما برای فهم بیشتر  این بخش به تمرینات این بخش سر بزنید.