考虑下图:
我试图找到一种方法来枚举从源节点到目标节点的所有可能路径。例如,从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
最佳答案
无论如何,我只是想知道是否有办法做到这一点,或者这可能是 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;
}
关于枚举所有可能路径的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3914842/