题目描述
假设无向图G采用邻接矩阵存储，设计一个算法，输出图G中从顶点u到v的所有简单路径。
输入
简单路径是指路径上的顶点不重复。第一行为一个整数n，表示顶点的个数（顶点编号为0到n-1），第二行表示顶点u和v的编号，接下来是为一个n*n大小的矩阵，表示图的邻接关系。数字为0表示不邻接，1表示不邻接。
输出
输出图G中从顶点u到v的所有简单路径。
样例输入
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
样例输出
0123
01243
013
03
04213
0423
043
#include <iostream> using namespace std; int n; int start,last; const int N = 1010; int st[N], path[N]; int g[N][N]; void dfs(int u, int t) { path[t] = u; if(u == last){ for(int i = 0; i < t; i++){ cout<<path[i]; } cout<<last<<endl; return; } st[u] = 1; for(int i = 0; i < n; i++){ if(st[i] == 0&&g[u][i]==1) dfs(i, t + 1); } st[u] = 0; } int main() { cin>>n; cin>>start>>last; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cin>>g[i][j]; } } dfs(start, 0); return 0; }
注释版
#include <iostream> using namespace std; int n;//点的个数 int start,last;//表示起点和终点 const int N = 1010; int st[N], path[N];//st[N]表示是否遍历过该点,path[N]存储路径 int g[N][N];//存地图 void dfs(int u, int t) { //将点存入路径中 path[t] = u; //如果这个点是终点，输出路径 if(u == last){ for(int i = 0; i < t; i++){ cout<<path[i]; } cout<<last<<endl; return; } //遍历过的点修改st为1 st[u] = 1; //如果下个点没有遍历过且与该点连通，继续遍历 for(int i = 0; i < n; i++){ if(st[i] == 0&&g[u][i]==1) dfs(i, t + 1); } //回溯过程再次修改为0 st[u] = 0; } int main() { cin>>n; cin>>start>>last; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cin>>g[i][j]; } } //从起点开始遍历, 0表示第一次 dfs(start, 0); return 0; }
