我如何才能找到(遍历)有向图中从/到给定节点的所有周期?
例如,我想要这样的东西:
A->B->A
A->B->C->A
而不是: B - > C > B
我如何才能找到(遍历)有向图中从/到给定节点的所有周期?
例如,我想要这样的东西:
A->B->A
A->B->C->A
而不是: B - > C > B
当前回答
我在搜索中找到了这个页面,由于循环与强连接组件不相同,我继续搜索,最后,我找到了一个高效的算法,它列出了有向图的所有(基本)循环。这篇论文来自唐纳德·b·约翰逊(Donald B. Johnson),可以在以下链接中找到:
http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF
java实现可以在下面找到:
http://normalisiert.de/code/java/elementaryCycles.zip
约翰逊算法的Mathematica演示可以在这里找到,实现可以从右边下载(“下载作者代码”)。
注:实际上,这个问题有很多算法。本文列举了其中一些:
http://dx.doi.org/10.1137/0205007
根据文章,Johnson的算法是最快的。
其他回答
在无向图的情况下,最近发表的一篇论文(无向图中循环和st路径的最优列表)提供了一个渐近最优解。你可以在这里阅读http://arxiv.org/abs/1205.2766或http://dl.acm.org/citation.cfm?id=2627951 我知道它不能回答你的问题,但由于你的问题标题没有提到方向,它可能仍然对谷歌搜索有用
我在搜索中找到了这个页面,由于循环与强连接组件不相同,我继续搜索,最后,我找到了一个高效的算法,它列出了有向图的所有(基本)循环。这篇论文来自唐纳德·b·约翰逊(Donald B. Johnson),可以在以下链接中找到:
http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF
java实现可以在下面找到:
http://normalisiert.de/code/java/elementaryCycles.zip
约翰逊算法的Mathematica演示可以在这里找到,实现可以从右边下载(“下载作者代码”)。
注:实际上,这个问题有很多算法。本文列举了其中一些:
http://dx.doi.org/10.1137/0205007
根据文章,Johnson的算法是最快的。
CXXGraph库提供了一组检测周期的算法和函数。
要获得完整的算法解释,请访问wiki。
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf
DFS c++版本的伪代码在二楼的答案:
void findCircleUnit(int start, int v, bool* visited, vector<int>& path) {
if(visited[v]) {
if(v == start) {
for(auto c : path)
cout << c << " ";
cout << endl;
return;
}
else
return;
}
visited[v] = true;
path.push_back(v);
for(auto i : G[v])
findCircleUnit(start, i, visited, path);
visited[v] = false;
path.pop_back();
}