алгоритм перечислить все возможные пути

Question

Рассмотрим следующий график:

Я пытаюсь найти способ, чтобы перечислить все возможные пути от узла-источника к целевому узлу. Так, например, от А до Е, мы имеем следующие возможные пути:

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

Заметим, что для C D E, есть фактически 2 пути, так как один из путей использует край F3, а другой использует край F5. Кроме того, поскольку существует цикл между A и C, вы можете получить бесконечное количество путей, но для целей этого меня интересуют только пути, в которых ни один узел не повторяется на пути от источника к цели.

Я написал алгоритм поиска с глубиной первого поиска (DFS), но проблема в том, что когда у вас есть несколько ребер между двумя узлами (например, ребра F3 и F5 выше), я не уверен, как с этим справиться. Мой алгоритм возвращает только пути A C D E и A C E, а не другие пути. В случае с A B C E я понимаю причину, потому что он начинается с A, а затем переходит на C и создает эти пути, но когда DFS возвращается к узлу B, он затем пытается перейти на C, но C уже был посещен поэтому он останавливается.

В любом случае, я просто задавался вопросом, есть ли способ сделать это, или, может быть, это NP-complete.

Если вы хотите увидеть мою 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 

Answer 1

Во всяком случае, я просто подумал, что есть способ сделать это, или, может быть, это NP-полной.
Я не верю, что вы можете вывести n! возможные пути в полиномиальное время. И так вы можете получить, если каждый узел подключен к другому узлу.

, но проблема в том, что, когда у вас есть несколько ребер между 2 узлами (например, ребер F3 и F5 выше)
Итак, вы хотите, чтобы рассмотреть края F3 и F5 быть такой же, верно? Вероятно, это самый простой способ просто удалить повторяющиеся края, прежде чем вы вызовете dfs.

, потому что он начинается с A, а затем переходит на C и создает эти пути, но когда DFS возвращается к узлу B, он затем пытается перейти на C, но C уже был посещен, поэтому он останавливается.
Хорошо, давайте отметим C, так как вас больше не посещают.

void dfs(char at) { 
    vis[at] = true; 

    // do stuff with 'at' 

    vis[at] = false; 
} 

Answer 2

Я думаю, что дубликат проблема путь будет также проявляться, если у вас есть сказать

J->K->L->O->T 
J->M->N->O->T 

Я думаю, что ваш «мы уже здесь, прежде чем» тест не должен просто смотреть на текущем узле, но путь, по которому вы туда попали. Поэтому не проверяйте «O», проверьте «JMNO» и «JKLO».