सी++ में स्रोत से लक्ष्य तक के सभी पथ

मान लीजिए कि हमारे पास एन नोड्स के साथ एक निर्देशित, चक्रीय ग्राफ है। हमें नोड 0 से नोड N-1 तक के सभी संभावित रास्तों को खोजना होगा, और उन्हें किसी भी क्रम में वापस करना होगा। ग्राफ़ इस प्रकार दिया गया है:नोड 0, 1, ..., ग्राफ़ हैं। लंबाई - 1. ग्राफ़ [i] सभी नोड्स की एक सूची है जिसके लिए किनारे (i, j) मौजूद हैं।

तो अगर इनपुट [[1,2], [3], [3], []] जैसा है, तो आउटपुट [[0,1,3], [0,2,3]] होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• Res नामक एक 2d सरणी बनाएं

• हल नामक एक विधि को परिभाषित करें, यह ग्राफ़, नोड, लक्ष्य और अस्थायी सरणी लेगा

• अस्थायी में नोड डालें

• यदि नोड लक्ष्य है, तो रेज़ में अस्थायी डालें और वापस लौटें

• मैं के लिए 0 से ग्राफ़ के आकार में [नोड] - 1

  • कॉल हल (ग्राफ, ग्राफ [नोड, आई], लक्ष्य, अस्थायी)

• मुख्य विधि से सरणी अस्थायी बनाएं, कॉल हल करें (ग्राफ, 0, ग्राफ़ का आकार -1, अस्थायी)

• रिटर्न रेस

उदाहरण(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, ],]