C ++中从源到目标的所有路径
假设我们有一个有N个节点的有向无环图。我们必须找到从节点0到节点N-1的所有可能路径，并以任何顺序返回它们。该图如下所示：节点为0、1，...，graph.length-1。graph[i]是存在边(i,j)的所有节点j的列表。
因此，如果输入类似于[[1,2]，[3]，[3]，[]]，则输出将为[[0,1,3]，[0,2,3]]。
为了解决这个问题，我们将遵循以下步骤-
制作一个称为res的2d数组
定义一个称为Solve的方法，它将采用图形，节点，目标和临时数组
将节点插入到临时
如果节点是目标，则将temp插入res并返回
对于i，范围为0到graph[node]的大小–1
调用solve（图，图[节点，i]，目标，温度）
从主要方法创建数组温度，调用solve（graph，0，graphsize-1，temp）
返回资源
例子（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, ],]