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

Question

سلام سال نو مبارک ازتون یه کمک میخوام:
میخوام تو نوشتن 2تا برنامه به زبان c++ کمکم کنید،
1-گراف را بگیرد و ماتریس مجاورت بدهد و بگوید چند مسیر به طول l دارد.
2-گراف را بگیرد و بگوید همبند است یا نه،اگر همبند است چندتا مولفه ی همبند دارد.

Answer 1

برای گرفتن ماتریس 3 تا کار میشه کرد

1_ لیست مجاورت ماتریس رو گرفت adjacency list

2_ماتریس مجاورت ماتریس رو گرفت adjacancy matrix

3_incidence matrix (معادل فارسی نداره ؟!)

 

برای گرفتن ماتریس به شکل لیست محاورت یکی از راه هاش استفاده از لیست پیوندی و ذخیره گراف در یک لیست 2 بعدی هستش .

list<list<int>>

ماتریس مجاورت به این شکله که سطر ها و سطون ها هر کدوم نشون دهنده یک راس هستن و اگر بین i , j یک یال باشه درایه معادله Aij رو 1 میزاریم در غیر این صورت 0

 

شکل زیر یک گراف به همراه لیست محاورتش :

 

 

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

#include <iostream>
#include <list>

using namespace std;

int  main()
{
    int vertexNumbers=0;

    cout<<"Number of  vertices : ";
    cin>>vertexNumbers;

    list<list<int>> graph(vertexNumbers);

    //get adjacent list of Graph
    int count=-1;
    for(list<list<int>>::iterator i=graph.begin();i!=graph.end();i++)
    {
        ++count;
        cout<<"Enter adjacent vertex to "<<count<<" <<-1 for end>>\n";
        list<int>& item= *i;
        while(true)
        {
            int g=0;
            cin>>g;
            if(g==-1)
                break;
            if(g>vertexNumbers||g<-1)
               cout<<"Wrong vertex  enter 0 To "<<vertexNumbers-1<<'\n';
            else
               item.push_back(g);
        }
     }


   int** adjMatrix=new int*[vertexNumbers];
   for(int i=0;i<vertexNumbers;i++)
   {
       adjMatrix[i]=new int[vertexNumbers];
       for(int j=0;j<vertexNumbers;j++)
           adjMatrix[i][j]=0;

   }
   
   //make adjacancy Matrix
   int row=0;
   for(list<list<int>>::iterator i=graph.begin();i!=graph.end();i++,row++)
   {
       list<int>& item= *i;
       for(list<int>::iterator j=item.begin();
           j!=item.end();
           j++)
       {
           adjMatrix[row][*j]=1;
       }

   }

   //show adj Matrix
   for(int i=0;i<vertexNumbers;i++)
   {
       for(int j=0;j<vertexNumbers;j++)
           cout<<adjMatrix[i][j];
       cout<<'\n';
   }
}

هرسوال رو جدا جدا بزار .

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