n个城市(n>2),指定两个城市,求这两个城市有几条路径?
发布网友
发布时间：2022-05-29 17:54
共1个回答
热心网友
时间：2023-10-30 19:55
#define CityNum 5
int AA[CityNum][CityNum]=
{ 1,0,1,0,0,
0,1,0,1,0,
0,1,1,0,0,
0,0,0,1,1,
0,0,1,0,1
};
int Path[CityNum]={0},pP=0;
int aFrom,bTo,pathCount=0;
int inPath(int a)
{
int j;
for(j=0;j<pP;j++)
if(Path[j]==a) return j;
return -1;
}
int FindPath(int a,int b)
{
int i,found=0,f1=0,f2=0;
if(AA[a][b]==1)
{
printf("----%d to %d\n",a,b);
found=1;
}
else for(i=0;i<CityNum;i++)
{
if(a==i)continue;
if(b==i)continue;
if(inPath(i)>=0)continue;
Path[pP++]=i;
f1=FindPath(a,i);
f2=FindPath(i,b);
found=f1&&f2;
pP--;
if(found)
{
printf(">>>>%d to %d\n",a,b);
if((a==aFrom)&&(b==bTo))
{
pathCount++;
printf("A path:%d+1 to %d+1.\n",aFrom,bTo);
printf("\n");
}
}
}
return found;
}
void main()
{
int a,b;
a=1,b=5;
aFrom=a-1;bTo=b-1;
Path[pP++]=aFrom;
Path[pP++]=bTo;
FindPath(aFrom,bTo);
printf("I have found %d path from %d to %d.\n",pathCount,a,b);
}追问根据AA数组的定义，从1到5应该只有一条路径（1->3->2->4->5）。结果算出来的是2条。我觉得是不是判断条件有问题。
追答#include
#define CityNum 5
int AA[CityNum][CityNum]={
1,0,1,1,0,
0,1,0,1,0,
0,1,1,0,0,
0,0,0,1,1,
0,0,1,0,1
};
int Path[CityNum],pP=0;
int aFrom,bTo,pathCount=0;
int inPath(int a){
int j;
for(j=0;j<pP;j++)if(Path[j]==a)return j;
return -1;
}
void GoPath(int a){
int i;
Path[pP++]=a;
if(a==bTo)
{
pathCount++;
printf("Path:");
for(i=0;i<pP;i++)printf("%d ",Path[i]);
printf("\n");
}
else for(i=0;i<CityNum;i++)if((inPath(i)<0)&&(AA[a][i]==1))GoPath(i);
Path[--pP];
}
void main(){
aFrom=0;bTo=4;
GoPath(aFrom);
printf("I have found %d path from %d to %d.\n",pathCount,aFrom,bTo);
}
