मान लीजिए हमारे पास 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 सरणी बनाएंsolveनामक एक विधि परिभाषित करें, यह ग्राफ, नोड, लक्ष्य और अस्थायी सरणी लेगाnodeकोtempमें डालें- यदि
node लक्ष्य है, तोtempकोresमें डालें और लौटें iको 0 सेgraph[node] का आकार - 1तक लूप करेंsolve(graph, graph[node, i], target, temp)कॉल करें
- मुख्य विधि से अस्थायी सरणी बनाएं,
solve(graph, 0, ग्राफ का आकार - 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, ],]
