搜索与图论：所有可达路径（DFS算法）

题目描述

题目描述
给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个函数，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。
输入描述
第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边

后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径

输出描述
输出所有的可达路径，路径中所有节点之间空格隔开，每条路径独占一行，存在多条路径，路径输出的顺序可任意。如果不存在任何一条路径，则输出 -1。

注意输出的序列中，最后一个节点后面没有空格！ 例如正确的答案是 1 3 5,而不是 1 3 5 ， 5后面没有空格！

输入示例

5 5
1 3
3 5
1 2
2 4
4 5

输出示例

1 3 5
1 2 4 5

参考代码

邻接表方法

#include <iostream>
#include <cstring>
#include <vector>using namespace std;const int N = 510;      // 边数int n, m;
int h[N], e[N], ne[N], idx;
vector<int> path;
bool flag;              // 用于标记是否存在路径void add(int a, int b)
{e[idx] = b; ne[idx] = h[a]; h[a] = idx; idx++;
}void dfs(int u)
{// 如果到达了终点，输出完整路径if (u == n){int len = path.size();  // 路径的长度for (int i = 0; i < len - 1; i++) printf("%d ", path[i]);printf("%d\n", path[len - 1]);flag = true;}// 如果没有到达终点，继续深搜，遍历该点的所有邻边for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];       // 邻边的终点path.push_back(j);  // 将下一个点加入路径dfs(j);             // 递归深搜path.pop_back();    // 弹出该邻边的终点，继续遍历下一个邻边}
}int main()
{memset(h, -1, sizeof h);scanf("%d%d", &n, &m);while (m -- ){int a, b;scanf("%d%d", &a, &b);add(a, b);}path.push_back(1);      // 先加入起点dfs(1);                 // 从起点开始深搜if (!flag) puts("-1");return 0;
}

邻接矩阵方法

#include <iostream>
#include <cstring>
#include <vector>using namespace std;const int N = 110;int n, m;
int g[N][N];
bool flag;
vector<int> path;void dfs(int u)
{// 如果到达了终点，输出完整路径if (u == n){int len = path.size();  // 路径的长度for (int i = 0; i < len - 1; i++) printf("%d ", path[i]);printf("%d\n", path[len - 1]);flag = true;}// 如果没有到达终点，继续深搜，遍历该点的所有邻边for (int i = 1; i <= n; i++){if (g[u][i] == 1){path.push_back(i);  // 将下一个点加入路径dfs(i);             // 递归深搜path.pop_back();    // 弹出该邻边的终点，继续遍历下一个邻边}}
}int main()
{scanf("%d%d", &n, &m);while (m -- ){int a, b;scanf("%d%d", &a, &b);g[a][b] = 1;                // 值为1代表右边，0代表无边}path.push_back(1);      // 先加入起点dfs(1);                 // 从起点开始深搜if (!flag) puts("-1");return 0;
}