算法训练 | 图论Part1 | 98.所有可达路径
目录
98.所有可达路径
深度搜索法
98.所有可达路径
-
题目链接：98. 所有可达路径
-
文章讲解：代码随想录
深度搜索法
-
代码一：邻接矩阵写法
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径void dfs (const vector<vector<int>>& graph, int x, int n) {// 当前遍历的节点x 到达节点n if (x == n) { // 找到符合条件的一条路径result.push_back(path);return;}for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点if (graph[x][i] == 1) { // 找到 x链接的节点path.push_back(i); // 遍历到的节点加入到路径中来dfs(graph, i, n); // 进入下一层递归path.pop_back(); // 回溯，撤销本节点}}
}int main() {int n, m, s, t;cin >> n >> m;// 节点编号从1到n，所以申请 n+1 这么大的数组vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));while (m--) {cin >> s >> t;// 使用邻接矩阵 表示无线图，1 表示 s 与 t 是相连的graph[s][t] = 1;}path.push_back(1); // 无论什么路径已经是从0节点出发dfs(graph, 1, n); // 开始遍历// 输出结果if (result.size() == 0) cout << -1 << endl;for (const vector<int> &pa : result) {for (int i = 0; i < pa.size() - 1; i++) {cout << pa[i] << " ";}cout << pa[pa.size() - 1] << endl;}
}
-
代码二：邻接表写法
#include <iostream>
#include <vector>
#include <list>
using namespace std;vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径void dfs (const vector<list<int>>& graph, int x, int n) {if (x == n) { // 找到符合条件的一条路径result.push_back(path);return;}for (int i : graph[x]) { // 找到 x指向的节点path.push_back(i); // 遍历到的节点加入到路径中来dfs(graph, i, n); // 进入下一层递归path.pop_back(); // 回溯，撤销本节点}
}int main() {int n, m, s, t;cin >> n >> m;// 节点编号从1到n，所以申请 n+1 这么大的数组vector<list<int>> graph(n + 1); // 邻接表while (m--) {cin >> s >> t;// 使用邻接表 ，表示 s -> t 是相连的graph[s].push_back(t);}path.push_back(1); // 无论什么路径已经是从0节点出发dfs(graph, 1, n); // 开始遍历// 输出结果if (result.size() == 0) cout << -1 << endl;for (const vector<int> &pa : result) {for (int i = 0; i < pa.size() - 1; i++) {cout << pa[i] << " ";}cout << pa[pa.size() - 1] << endl;}
}