برای گرفتن ماتریس 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 تا سوال که همبند بودن و پیدا کردن مسیر رو داخل دو تا سوال مجزا دیگه بپرس .