10

次のグラフについて考えてみます。

代替テキスト

ソースノードからターゲットノードへのすべての可能なパスを列挙する方法を見つけようとしています。たとえば、AからEまで、次のパスが考えられます。

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

ACDEの場合、パスの1つはエッジF3を使用し、もう1つはエッジF5を使用するため、実際には2つのパスがあることに注意してください。また、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
4

3 に答える 3

3

とにかく、これを行う方法があるのか​​、それともこれがNP完全であるのか疑問に思いました。多項式時間で可能なパスを
出力できるとは思いません。n!そして、それは、各ノードが互いに接続されている場合にどのように取得できるかです。

しかし、問題は、2つのノードの間に複数のエッジがある場合（上記のエッジF3とF5のように） 、エッジを考慮して同じにし
たいということですよね？を呼び出す前に、重複するエッジを削除するのがおそらく最も簡単なオプションです。 F3F5dfs

これは、Aから開始してCに移動し、それらのパスを構築しますが、DFSがノードBに戻ると、Cに移動しようとしますが、Cはすでにアクセスされているため、停止します。それでは、二度と訪問しないことを
マークしましょう。C

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

    // do stuff with 'at'

    vis[at] = false;
}
于 2010-10-12T13:03:29.207 に答える
0

私の推測では、あなたが言うなら、重複パスの問題も明らかになるでしょう

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

「以前にここにいたことがありますか」テストでは、現在のノードだけでなく、そこにたどり着いたパスを確認する必要があると思います。「O」はチェックせず、「JMNO」と「JKLO」をチェックしてください。

于 2010-10-12T13:15:25.657 に答える