algoritmo per enumerare tutti i possibili percorsi

Question

Si consideri il seguente grafico:

Sto cercando di trovare un modo per enumerare tutti i possibili percorsi da un nodo sorgente ad un nodo di destinazione. Ad esempio, da A a E, abbiamo le seguenti possibili percorsi:

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

noti che per A C D E, ci sono effettivamente 2 percorsi, in quanto uno dei percorsi usa bordo F3 e l'altro utilizza F5 bordo. Inoltre, poiché c'è un ciclo tra A e C, si potrebbe finire con un numero infinito di percorsi, ma per gli scopi di questo mi interessa solo i percorsi in cui nessun nodo è ripetuto sul percorso dalla sorgente alla destinazione.

Ho scritto un algoritmo di approfondimento prima ricerca (DFS), ma il problema è che quando si hanno più spigoli tra 2 nodi (come i bordi F3 e F5 sopra) non sono sicuro di come gestirlo. Il mio algoritmo riporta solo i percorsi A C D E e A C E, non gli altri percorsi. Nel caso di A B C E, ne capisco il motivo, perché inizia da A e quindi passa a C e crea quei percorsi, ma quando DFS torna al nodo B, tenta quindi di passare a C, ma C è già stato visitato così si ferma.

In ogni caso, mi sono chiesto se c'era un modo per farlo, o forse questo è NP-completo.

Nel caso in cui ti piacerebbe vedere il mio DFS, il codice è sotto (mi dispiace per l'abuso di macro, li uso nella programmazione di contest, quindi è un po 'un'abitudine).

#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; 
} 

uscita:

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

Answer 1

Comunque, ho solo chiesto se ci fosse un modo per fare questo, o forse questo è NP-completo.
Non credo che si possano produrre n! percorsi possibili in tempo polinomiale. Ed è così che puoi ottenere se ogni nodo è connesso l'uno all'altro.

ma il problema è che quando si hanno più spigoli tra i 2 nodi (come i bordi F3 e F5 sopra)
Quindi, si consiglia di considerare bordi F3 e F5 essere lo stesso, giusto? È probabilmente l'opzione più semplice per rimuovere solo i bordi duplicati prima di chiamare dfs, quindi. perché inizia da A e quindi passa a C e crea quei percorsi, ma quando DFS torna al nodo B, tenta quindi di passare a C, ma C è già stato visitato e quindi si ferma.
Bene, contrassegniamo C come non visitato di nuovo, quindi.

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

    // do stuff with 'at' 

    vis[at] = false; 
} 

Answer 2

La mia ipotesi è che il problema percorso duplicato sarà anche manifestare se avete dicono

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

Credo che la vostra "abbiamo stati qui prima" test non deve solo guardare il nodo corrente, ma il percorso attraverso il quale sei arrivato. Quindi non controllare "O", controllare "JMNO" e "JKLO".