سلام دوستان
من نميدونم يك گراف را چطور ميشه در c++ ایجاد کرد لطفا کمک کنید؟
Printable View
سلام دوستان
من نميدونم يك گراف را چطور ميشه در c++ ایجاد کرد لطفا کمک کنید؟
میتونی از لیست پیوندی یا جنرال لیست ها استفاده کنی. حتی به کمک آرایه هم میتونی این کار رو بکنی. ولی با آرایه سخت تره.
ميشه لطفا يك برنامه نمونش را برام بذاري؟
اين يك نمونه كد هست كه بهينه هم نوشته شده .اما به اين سئوال جواب داده شده قبلا . يك لينك هم مي ذارم تا بيشتر با گراف ها آشنا بشين .
[HTML]http://ce.sharif.edu/courses/85-86/2/ce153c/resources/root/Ch12-Data%20structures%20and%20Program%20Design%20in%20 C++.pdfکد:// m matrise mojaaverate yek graph (VertexNum=tedaade ra~s haa) ast,
// toole kootah tarin masir az rase n1 be n2, va -1 agar masir vojood nadaarad
// PassedVertexes is initially all zero, used inside the function to show
// the vertexes which are passed in the path
const VertexNum=3;
int PassedVertexes[]={0,0,0};
int ShortestPathLen(int m[][VertexNum],int n1,int n2)
{
int i,MinPathLen,l;
if(n1==n2)
return(0);
PassedVertexes[n1]=1; // passing the node n1 and try going to other nodes
MinPathLen=VertexNum; // longest possible path len is VertexNum-1
for(i=0;i<VertexNum;i++)
if(!PassedVertexes[i]&&m[n1][i])
{
l=ShortestPathLen(m,i,n2);
if(l>=0&&l<MinPathLen)
MinPathLen=l;
}
PassedVertexes[n1]=0; // back tracking in the path
if(MinPathLen==VertexNum)
return(-1);
else
return(1+MinPathLen);
}
[/HTML]
Good Luck :)
دو روش وجود داره:
1- ماتریس مجاورت (Adjacency matrix)
2- لیست
ماتریس زیر را در نظر بگیرید:
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
روش اول یه ماتریس n*n میگیریم (n تعداد ند ها) که اگه m[i][j] یک باشه یعنی از ند i به j یک یال داریم.
اگه صفر باشه یعنی این دو ند به هم وصل نیستند.
البته این روش حافظۀ زیادی نیاز داره و معمولاً در گراف هایی کاربرد داره که Dense هستند (یعنی بین اکثر ند هاشون یال هست)
به ماتریس زیر توجه کنید (مقدار عناصر خالی صفر هست):
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
اما روش دوم که روش لیست هست اینجوریه که یه لیست n تایی داریم.
هر عنصر نشان دهندۀ یک ند هست. در واقع هر کدام از این ندها یک لیست پیوندی اند که در صورتی که ند i به ند j متصل باشد ، در لیست ند i ، عدد j (شمارۀ ند مقصد) را ذخیره می کنیم.
به لیست های زیر توجه کنید:
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
مي خواهم گراف را خودم وارد برنامه كنم تا بهم جواب بده ؟نقل قول:
بك گراف چه طوري ساخته ميشه ؟نقل قول: