数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中从源到目标的所有路径
假设我们有一个具有 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 的二维数组
定义一个名为 solve 的方法，它将接收图、节点、目标和临时数组
将节点插入到临时数组中
如果节点是目标，则将临时数组插入到 res 中并返回
对于范围从 0 到 graph[node] 大小 - 1 的 i
调用 solve(graph, graph[node, i], target, temp)
从主方法创建数组 temp，调用 solve(graph, 0, graph 大小 - 1, temp)
返回 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, ],]
更新于： 2020年5月2日
421 次浏览
广告