#2
Edwardwang032012-12-19 20:25
|
首先贴上我自己写的反之被误认为不假思索求答案
程序代码:
int nextadj(AdjMatrix G, int u, int v,int *pre)
{
int i;
for (i = v; i < G.vexnum; i++)
if(G.arcs[u][i].adj != 0 && pre[i] == -1)
return i;
return -2;
}
int firstadj(AdjMatrix G, int u, int *pre)
{
int i;
for (i = 0; i < G.vexnum; i++)
if(G.arcs[u][i].adj != 0 && pre[i] == -1)
return i;
return -2;
}
void DFS_path(AdjMatrix G, int u, int v, int * pre)
{
int j;
for(j = firstadj(G, u, pre); j >= 0; j = nextadj(G, u, j, pre))
if(pre[j] == -1 )
{
if(j == v)
{
print_path(v, pre);
pre[v] = -1;
//return ;
}
else {DFS_path(G, j, v, pre);}
}
}
void all_path(AdjMatrix G, int u, int v)
{
//寻找两点之间所有路径
int *pre;
int i;
pre = (int *)malloc(sizeof(int));
for (i = 0; i < G.vexnum; i++)
pre[i] = -1;
pre[u] = u;
DFS_path(G, u, v, pre);
free(pre);
}
void print_path(int v, int *pre)
{
int i, j;
for(j = 0; j < 11; j++)
printf(" %d ",pre[j]);
getch();
printf("\n");
for(i = v; pre[i] != i; i = pre[i])
printf("%d<--",i);
printf("%d\n", pre[i]);
printf("\n路线相反\n");
}
{
int i;
for (i = v; i < G.vexnum; i++)
if(G.arcs[u][i].adj != 0 && pre[i] == -1)
return i;
return -2;
}
int firstadj(AdjMatrix G, int u, int *pre)
{
int i;
for (i = 0; i < G.vexnum; i++)
if(G.arcs[u][i].adj != 0 && pre[i] == -1)
return i;
return -2;
}
void DFS_path(AdjMatrix G, int u, int v, int * pre)
{
int j;
for(j = firstadj(G, u, pre); j >= 0; j = nextadj(G, u, j, pre))
if(pre[j] == -1 )
{
if(j == v)
{
print_path(v, pre);
pre[v] = -1;
//return ;
}
else {DFS_path(G, j, v, pre);}
}
}
void all_path(AdjMatrix G, int u, int v)
{
//寻找两点之间所有路径
int *pre;
int i;
pre = (int *)malloc(sizeof(int));
for (i = 0; i < G.vexnum; i++)
pre[i] = -1;
pre[u] = u;
DFS_path(G, u, v, pre);
free(pre);
}
void print_path(int v, int *pre)
{
int i, j;
for(j = 0; j < 11; j++)
printf(" %d ",pre[j]);
getch();
printf("\n");
for(i = v; pre[i] != i; i = pre[i])
printf("%d<--",i);
printf("%d\n", pre[i]);
printf("\n路线相反\n");
}
我的递归有问题还请指教,或者按照void DFS_path(AdjMatrix G, int u, int v, int * pre)写一个,其中u,v分别代表起点终点的编号,pre数组是记录每个的邻接点是否访问