C++ 中从源到目标的所有路径
c++server side programmingprogramming更新于 2024/9/1 6:16:00
假设我们有一个有 N 个节点的有向无环图。我们必须找到从节点 0 到节点 N-1 的所有可能路径，并以任意顺序返回它们。该图如下所示:节点为 0、1、...、graph.length - 1。graph[i] 是所有节点 j 的列表，其中边 (i, j) 存在。
因此，如果输入为 [[1,2], [3], [3], []]，则输出将为 [[0,1,3], [0,2,3]]。
为了解决这个问题，我们将遵循以下步骤 −
创建一个名为 res 的 2d 数组
定义一个名为 resolve 的方法，它将采用 graph、node、target 和 temp 数组
将节点插入 temp
如果节点是目标，则将 temp 插入 res 并返回
对于 i，范围为 0 到 graph[node] 的大小– 1
调用solve(graph, graph[node, i], target, temp)
从主方法创建数组temp，调用solve(graph, 0, size of graph - 1, temp)
return res
示例(C++)
让我们看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector < vector <int> > res;
void solve(vector < vector <int> >& graph, int node, int target, vector <int>temp){
temp.push_back(node);
if(node == target){
res.push_back(temp);
return;
}
for(int i = 0; i < graph[node].size(); i++){
solve(graph, graph[node][i], target, temp);
}
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector <int> temp;
solve(graph, 0, graph.size() - 1, temp);
return res;
}
};
main(){
vector<vector<int>> v = {{1,2},{3},{3},{}};
Solution ob;
print_vector(ob.allPathsSourceTarget(v));
}
输入
[[1,2],[3],[3],[]]
输出
[[0, 1, 3, ],[0, 2, 3, ],]
