bhossein
دوشنبه 18 دی 1391, 09:13 صبح
خواستم یه برنامه بنویسم که بین دو نقطه از گراف حداقل یه مسیر پیدا کنه. روشی که استفاده کردم این بود که در ماتریسی که سازنده اون گراف است نقطه شروع را پیدا کرده و تا زمانی که از به نقطه پایان نرسیده جستجو کند و نقطه پایان را بیابد.
قرار داد:
1-حلقه ها در مسیر وجود نداشته باشند.
(برای اینکار از ارایه ای به نام forbid استفاده کردم
پس از گرفتن نقطه شروع و درج آن در forbid و استک شروع به حرکت برای یافتن راس پایانی می کنیم.
برای اینکار در ماتریس شروع می کنیم به حرکت تا به یک برسیم. حال اگر اون 1 در آرایه ممنوعه ما بود یعنی این راس قبلا پیموده شده و باید از آن گذشت. اگر نبود درج آن در آرایه ممنوعه و استک و ادامه جستجو. اما اگر یک مسیر را تا انتها رفت. و به نقطه پایان نرسید برگردد و از استک و آرایه ممنوعه پاک شود و به راس قبلی برگردد و جستجو را ادامه دهد.
برنامه ای که نوشتم به شکل زیر ولی نمی دانم چرا در loop گیر می کند
#include <iostream>
#include <conio.h>
#include <stack>
using namespace std;
stack <int> man;
int main()
{
int v,n=0,i=0, j=0, a=0, b=0, c=0, d=0, x,flag2=0,flag=0, mat[10][10], forbid[80], arr[10], start, finish, fin2=11;
cout<<"hi.enter the count of vectore: ";
cin >> v;
cout <<endl<<"enter the vectores: ";
cout <<endl;
for (int a=0; a<v; a++)
cin >> arr[a];
// making matrix or graph//
for (int b=0; b<v; b++)
for (int c=0; c<v; c++)
{
cout <<"if <"<< arr[b] <<"> have relate with <"<< arr[c] <<"> press 1 else press 0: ";
cin >> mat[b][c];
cout << endl;
}
for (int b=0; b<v; b++)
{
for (int c=0; c<v; c++)
cout << mat[b][c]<<" ";
cout << endl;
}
//start & finish point//
cout<<"enter the start & finish point: ";
cout <<endl<<"start: ";
cin >> start;
cout <<endl<<"finish: ";
cin>> finish;
cout << endl;
//search//
for (int a=0; a<v; a++)
if (arr[a]==start)
{
forbid[n]=start;
n++;
man.push(arr[a]);
j=a;
}
while (fin2!=finish)
{
for (int i=0; i<v; i++)
{
if (mat[j][i]==1)
{
flag=1;
for (int b=0; b<n; b++)
if (forbid[b]==arr[i])
flag2=1;
if (flag2==0)
{
forbid[n]=arr[i];
n++;
man.push(arr[i]);
if (finish==arr[i])
{
fin2=finish;
flag=1;
break;
}
else if (arr[i]!=finish)
{
mat[j][i]=10;
mat[i][j]=10;
j=i;
i=0;
flag=0;
}
}
//for chek//
if (i==v && fin2!=finish && flag==0)
{
--n;
forbid[n]=0;
cout<<n;
man.pop();
for (c=0; c<v; c++)
if (man.top()==arr[c])
{
j=c;
i=0;
flag=0;
}
}
}
}
}
while (man.size()>0)
{
cout<<man.top()<<"->";
man.pop();
}
cin >> x;
getche();
return 0;
}
قرار داد:
1-حلقه ها در مسیر وجود نداشته باشند.
(برای اینکار از ارایه ای به نام forbid استفاده کردم
پس از گرفتن نقطه شروع و درج آن در forbid و استک شروع به حرکت برای یافتن راس پایانی می کنیم.
برای اینکار در ماتریس شروع می کنیم به حرکت تا به یک برسیم. حال اگر اون 1 در آرایه ممنوعه ما بود یعنی این راس قبلا پیموده شده و باید از آن گذشت. اگر نبود درج آن در آرایه ممنوعه و استک و ادامه جستجو. اما اگر یک مسیر را تا انتها رفت. و به نقطه پایان نرسید برگردد و از استک و آرایه ممنوعه پاک شود و به راس قبلی برگردد و جستجو را ادامه دهد.
برنامه ای که نوشتم به شکل زیر ولی نمی دانم چرا در loop گیر می کند
#include <iostream>
#include <conio.h>
#include <stack>
using namespace std;
stack <int> man;
int main()
{
int v,n=0,i=0, j=0, a=0, b=0, c=0, d=0, x,flag2=0,flag=0, mat[10][10], forbid[80], arr[10], start, finish, fin2=11;
cout<<"hi.enter the count of vectore: ";
cin >> v;
cout <<endl<<"enter the vectores: ";
cout <<endl;
for (int a=0; a<v; a++)
cin >> arr[a];
// making matrix or graph//
for (int b=0; b<v; b++)
for (int c=0; c<v; c++)
{
cout <<"if <"<< arr[b] <<"> have relate with <"<< arr[c] <<"> press 1 else press 0: ";
cin >> mat[b][c];
cout << endl;
}
for (int b=0; b<v; b++)
{
for (int c=0; c<v; c++)
cout << mat[b][c]<<" ";
cout << endl;
}
//start & finish point//
cout<<"enter the start & finish point: ";
cout <<endl<<"start: ";
cin >> start;
cout <<endl<<"finish: ";
cin>> finish;
cout << endl;
//search//
for (int a=0; a<v; a++)
if (arr[a]==start)
{
forbid[n]=start;
n++;
man.push(arr[a]);
j=a;
}
while (fin2!=finish)
{
for (int i=0; i<v; i++)
{
if (mat[j][i]==1)
{
flag=1;
for (int b=0; b<n; b++)
if (forbid[b]==arr[i])
flag2=1;
if (flag2==0)
{
forbid[n]=arr[i];
n++;
man.push(arr[i]);
if (finish==arr[i])
{
fin2=finish;
flag=1;
break;
}
else if (arr[i]!=finish)
{
mat[j][i]=10;
mat[i][j]=10;
j=i;
i=0;
flag=0;
}
}
//for chek//
if (i==v && fin2!=finish && flag==0)
{
--n;
forbid[n]=0;
cout<<n;
man.pop();
for (c=0; c<v; c++)
if (man.top()==arr[c])
{
j=c;
i=0;
flag=0;
}
}
}
}
}
while (man.size()>0)
{
cout<<man.top()<<"->";
man.pop();
}
cin >> x;
getche();
return 0;
}