所有可达路径
98. 所有可达路径 (kamacoder.com)
深度优先搜索,和之前的回溯题类似。
#include <iostream>
#include <vector>
using namespace std;
// 定义一个二维向量来存储所有可能的路径
vector<vector<int>> paths;
// 定义一个向量来存储当前路径
vector<int> path;
// 定义深度优先搜索函数
void dfs(const vector<vector<int>>& graph, int x, int n) {
// 如果到达节点n,将当前路径添加到所有路径中
if (x == n) {
paths.push_back(path);
return;
}
// 遍历所有可能的下一个节点
for (int i = 1; i <= n; i++) {
// 如果节点x和节点i之间有边(即连通)
if (graph[x][i] == 1) {
// 将节点i添加到当前路径
path.push_back(i);
// 递归地继续搜索从节点i开始的路径
dfs(graph, i, n);
// 回溯,移除节点i,尝试其他可能的路径
path.pop_back();
}
}
}
int main() {
int N, M; // N表示节点数量,M表示边的数量
cin >> N >> M; // 输入节点数量和边的数量
// 创建一个(N+1) x (N+1)的二维向量,初始化所有值为0
vector<vector<int>> graph(N + 1, vector<int>(N + 1, 0));
int s, t;
while (M--) { // 循环M次,输入每条边的两个节点
cin >> s >> t;
graph[s][t] = 1; // 表示节点s和节点t之间有边,即连通
}
// 从节点1开始搜索,将节点1添加到当前路径
path.push_back(1);
dfs(graph, 1, N); // 调用DFS函数搜索所有路径
// 如果没有找到路径,输出-1
if (paths.size() == 0)
cout << -1 << endl;
// 输出所有找到的路径
for (auto x : paths) {
for (int i = 0; i < x.size() - 1; i++) {
cout << x[i] << " ";
}
cout << x[x.size() - 1] << endl;
}
}
在构建图是,读入所有边,时间复杂度为O(M),在DFS是,最坏情况需要访问图中的每个节点和每天便,DFS的时间复杂度为O(N+M)。总的时间复杂度为O(N+M)。
空间复杂度,用邻接矩阵来存储graph信息需要(N+1)^2(从0到N+1的矩阵),paths在图全连接的情况下,可能要存储2^(N-1)条路(1-N),path为O(N),空间复杂度为O(2^(N-1))。
邻接链表参考
代码随想录 (programmercarl.com)
邻接数组也可以自己写写看。
所有可能的路径
797. 所有可能的路径 - 力扣(LeetCode)
上题的核心代码,代码如下,分析基本和上题相同。
class Solution {
public:
// 定义一个向量来存储当前路径
vector<int> path;
// 定义一个二维向量来存储所有可能的路径
vector<vector<int>> paths;
// 定义深度优先搜索函数
void dfs(const vector<vector<int>>& graph, int x, int n) {
// 如果到达目标节点n,将当前路径添加到所有路径中
if (x == n) {
paths.push_back(path);
return;
}
// 遍历当前节点的所有相邻节点
for (int i = 0; i < graph[x].size(); i++) {
// 将相邻节点添加到当前路径
path.push_back(graph[x][i]);
// 递归地继续搜索从相邻节点开始的路径
dfs(graph, graph[x][i], n);
// 回溯,移除刚刚添加的节点,以便尝试其他路径
path.pop_back();
}
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
// 目标节点是图的最后一个节点 graph.size() - 1
int n = graph.size() - 1;
// 从源节点0开始,将源节点添加到当前路径
path.push_back(0);
// 调用DFS函数搜索所有路径
dfs(graph, 0, n);
// 返回找到的所有路径
return paths;
}
};