BFS¶

الگوریتم bfs¶

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

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

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

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

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

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

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

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

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

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

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

درخت bfs¶

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

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

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

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

کد bfs¶

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

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

راه حل :

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

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

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

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 میشود و هر یال هم به ازای هر سر حداکثر یک بار صدا میشود پس الگوریتم ما از \(O(n+m)\) است.

نتیجه گیری¶

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

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

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