列举所有可能路径的算法

Question

请看下图：

我正在尝试找到一种方法来枚举从源节点到目标节点的所有可能路径。例如，从A到E，我们有以下可能的路径：

A B C D E
A B C E
A C D E
A C E

请注意，对于A C D E，实际上有2条路径，因为其中一条路径使用边F3，另一条路径使用边F5。另外，由于在A和C之间存在一个循环，所以最终可能会遇到无数的路径，但是出于这个目的，我只对在从源到目标的路径上没有节点重复的路径感兴趣。 >

我编写了深​​度优先搜索（DFS）算法，但是问题是，当您在2个节点之间有多个边（例如上面的边F3和F5）时，我不确定如何处理它。我的算法仅带回路径A C D E和A C E，不带其他路径。在A B C E的情况下，我理解了原因，因为它从A开始，然后转到C并构建这些路径，但是当DFS返回节点B时，它随后尝试转到C，但是C已经被访问过，因此停止了。

无论如何，我只是想知道是否有一种方法可以做到这一点，或者说这是NP完成的。

如果您想查看我的DFS，请在下面的代码中（对宏的滥用，很抱歉，我在竞赛编程中使用了它们，因此有点习惯）。

#include <algorithm>
#include <numeric>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <cmath>
#include <complex>
#include <stack>
#include "time.h"
using namespace std;
#define SZ(x) (int)x.size()
#define FOR(i,x,y) for(int i=(int)(x);i<=(int)(y);++i)
#define REP(i,n) FOR(i,0,n-1)
#define FORD(i,x,y) for(int i=(int)(x);i>=(int)(y);--i)
#define ALL(a) (a).begin(),(a).end()
#define FORE(i,t) for(i=t.begin();i!=t.end();++i)
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<double> VD;
typedef deque<int> DI;
typedef deque<string> DS;
typedef long long i64;
#define PI 3.14159265358979323
#define DEGTORAD(x) (double)x * 3.14159265358979323846264338327950288 / 180.0
#define RADTODEG(x) (double)x * 180 / 3.14159265358979323846264338327950288
#define prt if(1)printf
template <typename T> string tostr(const T& t) { ostringstream os; os<<t; return os.str(); } 

typedef pair< char, char > PCC;
map< PCC, int > adj;
map< char, bool > vis;

vector< char > path;

void dfs(char at) {
  if (at == 'E') {
    REP(i,SZ(path)) {
      if (i != 0)
        cout<<",";
      cout<<path[i];
    }
    cout<<",E"<<endl;
    return;
  }
  if (vis[at])
    return;
  vis[at] = true;
  map< PCC, int >::iterator it;
  FORE(it,adj) {
    if (it->first.first == at) {
      path.push_back(it->first.first);
      dfs(it->first.second);
      path.erase(path.end()-1);
    }
  }
}


int main() {
  adj[make_pair('A','B')] = 1;
  adj[make_pair('A','C')] = 1;
  adj[make_pair('C','D')] = 1;
  adj[make_pair('D','E')] = 1;
  adj[make_pair('E','I')] = 1;
  adj[make_pair('C','F')] = 1;
  adj[make_pair('F','G')] = 1;
  adj[make_pair('F','H')] = 1;
  adj[make_pair('C','E')] = 1;
  dfs('A');
  return 0;
}
输出：

---------- Capture Output ----------
A,C,D,E
A,C,E

请考虑下图：我正在尝试找到一种枚举从源节点到目标节点的所有可能路径的方法。例如，从A到E，我们有以下可能的路径：A B C D E ...

Answer 1

[[无论如何，我只是想知道是否有一种方法可以做到这一点，或者也许这是NP完成的。

Answer 2

我的猜测是如果您说重复路径问题也会出现

Answer 3

这是使用

BFS