الگوریتم تست کردن همبند بودن گراف

Question

2-گراف را بگیرد و بگوید همبند است یا نه،اگر همبند است چندتا مولفه ی همبند دارد

Comments

احتمالا با BFS بشه همچین کاری کرد. من این مطلب رو نخوندم اما شما یه نگاه بندازید.

Answer 1

برای چک کردن همبند بودن از الگوریتم های جست و جوی گراف مثل DFS یا BFS  استفاده میشه.

برای  نوشتن DFS به این شکل عمل می کنیم :

 1_ یک صف(Queue) میسازیم و بهش مقدار اولیه میدیم

 2_ عنصر اول صف رو از صف خارج می کنیم (deque)

 3_ عنصر خارج شده رو گشترش میدیم و به اول صف اضافه می کنیم(enque) و اگر قابل گسترش نبود دیگه به صف اضافش نمی کنیم

 4_ مرحله 2 به بعد رو تا وقتی که صف خالی نشده تکرار می کنیم

 

دقت کنید اگر در مرحله 3 عنصر رو به جای اول صف به آخر صف اضافه کنیم الگوریتم به راحتی به BFS تبدیل میشه .

 

مثلا فرض کنید گراف ما به این شکله :

 

 

و فرض کنید DFS  رو از راس A شروع می کنیم مراحل به این شکله :

(A,B),(A,C)                      ساختن و  مقدار اولیه دادن  
(A,B,D),(A,B,C),(A,C)       گسترش (A,B) , اضافه کردن به اول صف  
(A,B,D,E),(A,B,C),(A,C)   گسترش (A,B,D) , اضافه کردن به اول صف  
(A,B,C),(A,C)                  گسترش (A,B,D,E) , چون قابل گسترش نیست از صف حذف میشه  
(A,C)                              گسترش (A,C) , چون یکبار قبلا گسترش داده شده از صف حذف میشه  
--                                    تمام

 

حالا برای چک کردن همبندی کافیه که DFS  رو انجام بدیم و راس هایی که ازشون می گذریم رو مارک دار کنیم اگر بعد از پایان DFS همه راس ها مارک دار بودند گراف همبنده .

این شبه کد برنامه ( از این آدرس )

test-connected(G)
{
  choose a vertex x
  make a list L of vertices reachable from x,
  and another list K of vertices to be explored.
  initially, L = K = x.

  while K is nonempty
      find and remove some vertex y in K
      for each edge (y,z)
          if (z is not in L)
          add z to both L and K

  if L has fewer than n items
      return disconnected
  else return connected
}

اینم کد ++C (کد رو الان نوشتم. کامل تست نشده شاید درست کار نکنه )

ورودی تابع ماتریس مجاورت به همراه تعداد راس هاست .

bool isConnective(int** adjMatrix,int vertexNumbers)
{
    deque<vector<int>> container;

    std::set<int> findValues;

    //meghdar avalie
    findValues.emplace(0);
    for(int j=0;j<vertexNumbers;j++)
    {
        if(adjMatrix[0][j]==1)
        {
           vector<int> mval;
           mval.push_back(0);
           mval.push_back(j);
           findValues.emplace(j);
           container.push_front(mval);
        }
    }

    //
    while(container.size()!=0)
    {
        vector<int> item=container.front();
        container.pop_front();
        int tailLoc=item[item.size()-1];

        for(int j=0;j<vertexNumbers;j++)
        {
            if(adjMatrix[tailLoc][j]==1)
            {
                //agar onsor ghablan peymayesh nashode
                if(find(item.begin(),item.end(),j)==item.end())
                {
                    vector<int> mval(item);
                    mval.push_back(j);
                    findValues.emplace(j);
                    container.push_front(mval);
                }
            }
        }
    }

    if(findValues.size()==vertexNumbers)
        return true;
    else
        return false;

}