C语言打印图中两点之间的所有路径,不是最短路径!!!谢谢高手麻烦帮忙
代码要实现哈!
领接矩阵的哈,谢谢了,思想也要的!
这是我写的程序和运行的结果,如果有不会的地方依然可以问我。
/*
首先我想说明几点问题。
1.我不知道你的题意中的路径是单向的还是双向的,不过我把路径设置成双向的了
2.说一下我程序的输入,首先输入一个n,表示该图中有n条路;然后有n行,每行
两个数x, y(1<=x, y<=99),表示这两个地点有一条路径。最后输入两个数,
表示计算这两点之间所有的路径
3.我的思路用的是深搜,不过广搜也是可以的
*/
#include <stdio.h>
#include <math.h>
int path[100][100];///path[i][j]为0表示i, j两点之间不通,为1表示有一条路
int stack[120], m=1, n, x, y;///存储路径
void dfs(int p)
{
int i, j;
for(i=1; i<=100; i++)
{
if(path[p][i]==1)
{
if(i == y)///如果深搜到了终点,就输出刚才经过的路径
{
for(j=0; j<m; j++)
{
printf("%-5d", stack[j]);
}
printf("%-5d\n", y);
}
else///如果该点不是终点
{
stack[m] = i;///将该点存起来
m++;
dfs(i);///接着深搜
m--;
}
}
}
}
int main()
{
int i, j;
memset(path, 0, sizeof(path));
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d %d", &x, &y);
path[x][y] = path[x][y] = 1;///这两点之间有路径
}
scanf("%d %d", &x, &y);
stack[0] = x;
dfs(x);
}
追问你说的方法是这个,可是我的是两点之间的,采用领接矩阵的存储的,你能用下面这个函数帮我实现吗?谢谢!void allpath(graps G,int a,int b )a表示出发点的编号,b表示终点的编号,
追答/*
首先我想说明几点问题。
你给的信息太少了,所以我只能自己假定某些条件,然后去实现程序。
1.我是在原来的程序上稍微改动了一下。
2.程序中的路径这次设为单项的,graph[i][j]表示从i到j有一条路径,而不能表示从j到i
也有一条路径。这点要注意
3.设定矩阵中只有0和1,1表示有一条路径,0表示没有路径
4.设定该程序的输入格式为:首先输入一个n表示一共有n个节点;然后输入n*n的矩阵;
最后输入两个数x,y(1
#include
int graph[100][100];///graph[i][j]为0表示i, j两点之间不通,为1表示有一条路
int stack[120], m=1, n, x, y;///存储路径
void dfs(int p)
{
int i, j;
for(i=1; i<=n; i++)
{
if(graph[p][i]==1)
{
if(i == y)///如果深搜到了终点,就输出刚才经过的路径
{
for(j=0; j<m; j++)
{
printf("%-5d", stack[j]);
}
printf("%-5d\n", y);
}
else///如果该点不是终点
{
graph[p][i] = 0;
stack[m] = i;///将该点存起来
m++;
dfs(i);///接着深搜
graph[p][i] = 1;
m--;
}
}
}
}
int main()
{
int i, j, t;
scanf("%d", &n);
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
scanf("%d", &t);
graph[i][j] = t;
}
}
scanf("%d %d", &x, &y);
stack[0] = x;
dfs(x);
}
void allway3(Graps *G)
{ wenjian(G);
printf("请输入你的起始景点的名字:\n");
char a[15],b[15];
scanf("%s%s",a,b);
int m,n;//接受返回来的编号
m=Locatidever(G,a);
n=Locatidever(G,b);
//printf("%d %d\n",m,n);
stack[0]=m;
int k;
k=0;
allpath(G,m,n,k);//数组下标的传递
m,n表其气势终点哈你帮我写下allpath(G,m,n,k)函数和写改下算法就行,谢谢!
}
高手,我说的是所有路径呀不是你说的那个算法,任然谢谢!
你能帮我用无向图的领接矩阵处理吗,谢谢!q806970740
void allway3(Graps *G)
{ wenjian(G);
printf("请输入你的起始景点的名字:\n");
char a[15],b[15];
scanf("%s%s",a,b);
int m,n;//接受返回来的编号
m=Locatidever(G,a);
n=Locatidever(G,b);
//printf("%d %d\n",m,n);
stack[0]=m;
int k;
k=0;
allpath(G,m,n,k);//数组下标的传递