首页 > 代码库 > 邻接矩阵存储简单路径(swust oj 1070)
邻接矩阵存储简单路径(swust oj 1070)
Description
假设无向图G采用邻接矩阵存储，设计一个算法，输出图G中从顶点u到v的所有简单路径。
Input
简单路径是指路径上的顶点不重复。第一行为一个整数n，表示顶点的个数（顶点编号为0到n-1），第二行表示顶点u和v的编号，接下来是为一个n*n大小的矩阵，表示图的邻接关系。数字为0表示不邻接，1表示不邻接。
Output
输出图G中从顶点u到v的所有简单路径。
Sample Input
5
0 3
0 1 0 1 1
1 0 1 1 0
0 1 0 1 1
1 1 1 0 1
1 0 1 1 0
Sample Output
0123
01243
013
03
04213
0423
043
PE代码：（学校oj有点水，格式键值搞不懂）
#include<stdio.h>#include<string.h>int map[1100][1100];//存地图int point;struct a//记录当前位置{ int now;}q[10000];int start,end;//起止点int vis[10000];//标记void print(int h)//打印函数{ for(int i=0;i<=h;i++) printf("%d",q[i].now); printf("\n");}void DFS(int x)//深度搜索{ if(q[x].now==end){ print(x); return; } for(int i=0;i<point;i++) if(map[i][q[x].now]==1&&vis[i]==0){ q[x+1].now=i; vis[i]=1;//标记 DFS(x+1); vis[i]=0;//标记解除 }}int main(){ scanf("%d",&point); scanf("%d%d",&start,&end); for(int i=0;i<point;i++) for(int j=0;j<point;j++) scanf("%d",&map[i][j]);// q[0].front=-1; vis[0]=1; q[0].now=start; DFS(0); return 0;}/*50 30 1 0 1 11 0 1 1 00 1 0 1 1 1 1 1 0 11 0 1 1 0*/+
邻接矩阵存储简单路径(swust oj 1070)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。