Algorithmus alle möglichen Pfade zum Aufzählen

Question

Sie sich das folgende Diagramm:

Ich versuche, einen Weg zu finden, alle möglichen Pfade von einem Quellknoten zu einem Zielknoten aufzuzählen. Zum Beispiel von A bis E, haben wir die folgenden möglichen Pfade:

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

beachte, daß für A C D E, gibt es tatsächlich 2 Wege, da einer der Pfade nutzt Kante F3 und die anderen Verwendungen Kanten F5. Da auch ein Zyklus zwischen A und C gibt es, könnte man mit einer unendlichen Anzahl von Pfaden enden, aber für die Zwecke dieses Ich bin nur daran interessiert, Pfade, in denen kein Knoten auf dem Weg von der Quelle zum Ziel wiederholt wird.

Ich schrieb eine Tiefensuche (DFS) -Algorithmus, aber das Problem ist, dass, wenn Sie mehrere Kanten zwischen zwei Knoten (wie Kanten F3 und F5 oben) haben ich bin nicht sicher, wie es zu handhaben. Mein Algorithmus bringt nur zurück Pfade A C D E und A C E, nicht die anderen Wege. Im Falle von A B C E, verstehe ich den Grund, weil es bei A beginnt und geht dann zu C und baut diese Pfade, aber wenn der DFS zu Knoten B zurückkommt, versucht es dann zu C zu gehen, aber C bereits besucht so dass es aufhört.

Wie auch immer, ich frage mich, ob es ein Weg, dies zu tun, oder vielleicht ist NP-vollständig.

Falls Sie mögen meine DFS sehen, Code ist unten (sorry für den Makro Missbrauch, verwende ich diese in Wettbewerb Programmierung, so dass es ein bisschen einer Gewohnheit ist).

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

Ausgabe:

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

Answer 1

Wie auch immer, ich frage mich, ob es ein Weg, dies zu tun, oder vielleicht ist NP-vollständig.
Ich glaube nicht, Sie Ausgabe n! möglichen Pfade in Polynomzeit können. Und das ist, wie können Sie, wenn jeder Knoten erhalten zu jedem anderen Knoten verbunden ist.

aber das Problem ist, dass, wenn Sie mehrere Kanten zwischen zwei Knoten (wie Kanten F3 und F5 oben)
Also, wollen Sie Kanten F3 und F5 gleich sein, richtig zu beachten? Es ist wahrscheinlich die einfachste Möglichkeit, nur doppelte Kanten zu entfernen, bevor Sie dfs rufen, dann.

, weil es bei A beginnt und geht dann zu C und baut diese Pfade, aber wenn die DFS zurück zu Knoten B erhält, versucht es dann zu C zu gehen, aber C bereits besucht, so stoppt sie.
Nun, lassen Sie uns Zeichen C nicht wieder besucht, dann.

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

    // do stuff with 'at'

    vis[at] = false;
}

Answer 2

Meine Vermutung ist, dass der doppelte Weg Problem wird auch manifestieren, wenn Sie sagen

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

Ich denke, Ihr „haben wir schon hier, bevor“ Test sollte nicht nur auf den aktuellen Knoten aus, aber der Weg, auf dem du hast es. So prüft nicht für "O", die Prüfung für "jmno" und "JKLO".