C ++中从源到目标的所有路径

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个有N个节点的有向无环图。我们必须找到从节点0到节点N-1的所有可能路径，并以任何顺序返回它们。该图如下所示：节点为0、1，...，graph.length-1。graph [i]是存在边(i,j)的所有节点j的列表。

因此，如果输入类似于[[1,2]，[3]，[3]，[]]，则输出将为[[0,1,3]，[0,2,3]]。

为了解决这个问题，我们将遵循以下步骤-

  • 制作一个称为res的2d数组

  • 定义一个称为Solve的方法，它将采用图形，节点，目标和临时数组

  • 将节点插入到临时

  • 如果节点是目标，则将temp插入res并返回

  • 对于i，范围为0到graph [node]的大小– 1

    • 调用solve（图，图[节点，i]，目标，温度）

  • 从主要方法创建数组温度，调用solve（graph，0，graph size-1，temp）

  • 返回资源

例子（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, ],]

以上是 C ++中从源到目标的所有路径 的全部内容， 来源链接： utcz.com/z/343576.html

回到顶部