算法枚举所有可能的路径 [英] algorithm to enumerate all possible paths
问题描述
考虑如下图：
我试图找到一种方法来枚举到目标节点从源节点的所有可能路径。例如，从A到E，我们有以下可能的路径：
A B C D E
A B CË
A C D E
高手
请注意，对于ACDE，实际上有2路径中，由于路径之一使用边缘F3和另一种使用边缘F5。此外，由于有A和C之间的循环，你可能最终与路径无限多，但是本作的目的，我只关心在没有节点重复从源到目标的路径上的路径。
我写了一个深度优先搜索（DFS）的算法，但问题是，当你有2个节点之间的多条边（如边F3和F5以上）我不知道如何处理它。我的算法只带回路径 ACDE 和 ACE ，而不是其他的路径。在 ABCE 的情况下，我明白其中的道理，因为它开始于A，然后进入C和构建这些路径，但是当DFS回来到节点B，它然后尝试去C，但C已经已经访问过，因此停止。
反正，我只是想知道是否有一种方法可以做到这一点，也许这是NP完全问题。
如果你想看到我的DFS，code是低于（对不起宏观虐待，我在比赛编程中使用这些所以这是一个有点习惯）。
的#include＆LT;算法＆GT;
＃包括＆LT;数字＆GT;
＃包括＆LT;的iostream＆GT;
＃包括＆LT; sstream＆GT;
＃包括＆LT;字符串＆GT;
＃包括＆LT;载体＆GT;
＃包括＆LT;排队＆GT;
＃包括＆LT;双端队列＆GT;
＃包括＆LT;集＆gt;
＃包括＆LT;地图＆GT;
＃包括＆LT; cstdio＆GT;
＃包括＆LT; cstdlib＆GT;
＃包括＆LT; cctype＆GT;
＃包括＆LT;＆了cassert GT;
＃包括＆LT; CMATH＆GT;
＃包括＆LT;复杂＆GT;
＃包括＆LT;栈＆GT;
的#includetime.h中
使用名字空间std;
的#define SZ（x）的（中间体）x.size（）
#define定义（I，X，Y）的for（int i =（int）的（X）; I＆LT; =（INT）（Y）; ++ I）
的#define REP（I，N）（Ⅰ，0，N-1）
的#define福特（ⅰ，X，Y）为（INT I =（int）的（x）的; I＆GT; =（int）的（γ）; - 一）
的#define ALL（A）（A）.begin（）中，（a）.end关于（）
＃定义FORE（I，T）为（I = t.begin（！）; I = t.end（）; ++ I）
的typedef矢量＆lt; INT＆GT;六;
的typedef矢量＆lt;串GT; VS;
类型定义矢量＆lt;布尔＆GT; VB;
类型定义矢量＆lt;双＆GT; VD;
的typedef双端队列＆LT; INT＆GT; DI;
的typedef双端队列＆LT;字符串＆GT; DS;
的typedef长长I64;
＃定义PI 3.14159265358979323
＃定义DEGTORAD（X）（双）X * 3.14159265358979323846264338327950288 / 180.0
＃定义RADTODEG（X）（双）X * 180 / 3.14159265358979323846264338327950288
的#define PRT如果（1）的printf
模板＆LT; typename的T＆GT;字符串tostr（const的T＆amp; T公司）{ostringstream操作系统; OS＆LT;＆LT;吨;返回os.str（）; }
的typedef对＆LT;焦炭，焦炭和GT; PCC;
地图＆LT; PCC，INT＆GT;形容词;
地图＆LT;焦炭，布尔＆GT;可见;
矢量＆lt;焦炭＆GT;路径;
无效DFS（字符的）{
如果（在=='E'）{
REP（我，SZ（路径））{
如果（ⅰ！= 0）
的cout＆其中;＆所述;，;
COUT＆LT;＆LT;路径[I]
}
COUT＆LT;＆LT;E＆LT;＆LT; ENDL;
返回;
}
如果（相[在]）
返回;
可见[在] =真;
地图＆LT; PCC，INT＆GT;：迭代它;
FORE（它，形容词）{
如果（IT-＆GT; first.first == AT）{
path.push_back（IT-＆GT; first.first）;
DFS（IT-＆GT; first.second）;
path.erase（path.end（） - 1）;
}
}
}
诠释的main（）{
形容词[make_pair（'A'，'B'）] = 1;
形容词[make_pair（'A'，'C'）] = 1;
形容词[make_pair（C，D）] = 1;
形容词[make_pair（'D'，'E'）] = 1;
形容词[make_pair（'E'，'我'）] = 1;
形容词[make_pair（C，F）] = 1;
形容词[make_pair（F，G'）] = 1;
形容词[make_pair（F，H）] = 1;
形容词[make_pair（'C'，'E'）] = 1;
DFS（'A'）;
返回0;
}
输出：
----------捕获输出----------
A，C，D，E
高手
无论如何，我只是想知道是否有一种方法可以做到这一点，也许这是NP完全问题。的
我不相信你可以输出 N！在多项式时间可能的路径。这就是如何可能你如果每个节点都连接到彼此节点
但问题是，当你有2个节点之间的多条边（如边F3和F5以上）的
所以，你要考虑的边缘 F3 和 F5 是一样的，对不对？这可能只是删除重复的边缘，你叫 DFS ，然后才最简单的选择。
，因为它开始于A，然后进入C和构建这些路径，但是当DFS回来到节点B后，就会试图去C，但C处已经被访问过，因此停止。的
好吧，让我们纪念 C 不会再次访问的话。
无效DFS（字符的）{
可见[在] =真;
//做的东西跟'在'
可见[在] = FALSE;
}
Consider the following graph:
I'm trying to find a way to enumerate all possible paths from a source node to a target node. For example, from A to E, we have the following possible paths:
A B C D E
A B C E
A C D E
A C E
Note that for A C D E, there are actually 2 paths, since one of the paths uses edge F3 and the other uses edge F5. Also, since there's a cycle between A and C, you could end up with an infinite number of paths, but for the purposes of this I'm only interested in paths in which no node is repeated on the path from source to target.
I wrote a depth first search (DFS) algorithm, but the problem is that when you have multiple edges between 2 nodes (like edges F3 and F5 above) I'm not sure how to handle it. My algorithm only brings back paths A C D E and A C E, not the other paths. In the case of A B C E, I understand the reason, because it starts at A and then goes to C and builds those paths, but when the DFS gets back to node B, it then tries to go to C, but C has already been visited so it stops.
Anyway, I just wondered if there was a way to do this, or maybe this is NP-complete.
In case you'd like to see my DFS, code is below (sorry for the macro abuse, I use these in contest programming so it's a bit of a habit).
#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;
}
Output:
---------- Capture Output ----------
A,C,D,E
A,C,E
Anyway, I just wondered if there was a way to do this, or maybe this is NP-complete.
I don't believe you can output n! possible paths in polynomial time. And that's how may you get if each node is connected to each other node.
but the problem is that when you have multiple edges between 2 nodes (like edges F3 and F5 above)
So, you want to consider edges F3 and F5 to be the same, right? It's probably the simplest option to just remove duplicate edges before you call dfs, then.
because it starts at A and then goes to C and builds those paths, but when the DFS gets back to node B, it then tries to go to C, but C has already been visited so it stops.
Well, let's mark C as not visited again, then.
void dfs(char at) {
vis[at] = true;
// do stuff with 'at'
vis[at] = false;
}
这篇关于算法枚举所有可能的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
