Giả sử chúng ta có một đồ thị có hướng, xoay chiều với N nút. Chúng ta phải tìm tất cả các đường đi có thể từ nút 0 đến nút N-1 và trả về chúng theo thứ tự bất kỳ. Biểu đồ được đưa ra như sau:các nút là 0, 1, ..., graph.length - 1. graph [i] là danh sách tất cả các nút j mà cạnh (i, j) tồn tại.
Vì vậy, nếu đầu vào là [[1,2], [3], [3], []], thì đầu ra sẽ là [[0,1,3], [0,2,3]].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Tạo một mảng 2d được gọi là res
-
Xác định một phương thức được gọi là giải quyết, điều này sẽ lấy đồ thị, nút, đích và mảng tạm thời
-
chèn nút vào tạm thời
-
nếu nút là đích, thì chèn tạm thời vào res và trả về
-
cho tôi trong phạm vi từ 0 đến kích thước của biểu đồ [node] - 1
-
gọi giải quyết (đồ thị, đồ thị [nút, i], mục tiêu, tạm thời)
-
-
Từ phương thức chính, tạo mảng tạm thời, gọi giải quyết (đồ thị, 0, kích thước của đồ thị - 1, tạm thời)
-
trả lại res
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -
#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));
} Đầu vào
[[1,2],[3],[3],[]]
Đầu ra
[[0, 1, 3, ],[0, 2, 3, ],]