我如何才能找到(遍历)有向图中从/到给定节点的所有周期?
例如,我想要这样的东西:
A->B->A
A->B->C->A
而不是: B - > C > B
我如何才能找到(遍历)有向图中从/到给定节点的所有周期?
例如,我想要这样的东西:
A->B->A
A->B->C->A
而不是: B - > C > B
当前回答
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();
}
其他回答
我在搜索中找到了这个页面,由于循环与强连接组件不相同,我继续搜索,最后,我找到了一个高效的算法,它列出了有向图的所有(基本)循环。这篇论文来自唐纳德·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的算法是最快的。
关于你关于排列周期的问题,请在这里阅读更多: https://www.codechef.com/problems/PCYCLE
您可以尝试以下代码(输入大小和数字number):
# include<cstdio>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int num[1000];
int visited[1000]={0};
int vindex[2000];
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
int t_visited=0;
int cycles=0;
int start=0, index;
while(t_visited < n)
{
for(int i=1;i<=n;i++)
{
if(visited[i]==0)
{
vindex[start]=i;
visited[i]=1;
t_visited++;
index=start;
break;
}
}
while(true)
{
index++;
vindex[index]=num[vindex[index-1]];
if(vindex[index]==vindex[start])
break;
visited[vindex[index]]=1;
t_visited++;
}
vindex[++index]=0;
start=index+1;
cycles++;
}
printf("%d\n",cycles,vindex[0]);
for(int i=0;i<(n+2*cycles);i++)
{
if(vindex[i]==0)
printf("\n");
else
printf("%d ",vindex[i]);
}
}
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();
}
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf
我曾经在面试中遇到过这样的问题,我怀疑你遇到过这种情况,你来这里寻求帮助。把这个问题分解成三个问题就容易多了。
如何确定下一个有效点 路线 你如何确定一个点是否存在 被使用 你如何避免越过 同样的观点
问题1) 使用迭代器模式提供迭代路由结果的方法。放置获取下一个路由的逻辑的一个好地方可能是迭代器的“moveNext”。要找到有效的路由,这取决于您的数据结构。对我来说,这是一个sql表充满有效的路由可能性,所以我必须建立一个查询,以获得有效的目的地给定的源。
问题2) 当您找到每个节点时,将它们推入一个集合,这意味着您可以通过动态询问正在构建的集合,很容易地查看是否在某个点上“返回”。
问题3) 如果在任何时候你看到你正在折回,你可以从集合中弹出东西并“后退”。然后从这一点开始,再次尝试“前进”。
黑客:如果你正在使用Sql Server 2008,有一些新的“层次结构”的东西,你可以用它来快速解决这个问题,如果你把你的数据结构成树状。