資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告