我如何才能找到(遍历)有向图中从/到给定节点的所有周期?
例如,我想要这样的东西:
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的算法是最快的。
其他回答
我曾经在面试中遇到过这样的问题,我怀疑你遇到过这种情况,你来这里寻求帮助。把这个问题分解成三个问题就容易多了。
如何确定下一个有效点 路线 你如何确定一个点是否存在 被使用 你如何避免越过 同样的观点
问题1) 使用迭代器模式提供迭代路由结果的方法。放置获取下一个路由的逻辑的一个好地方可能是迭代器的“moveNext”。要找到有效的路由,这取决于您的数据结构。对我来说,这是一个sql表充满有效的路由可能性,所以我必须建立一个查询,以获得有效的目的地给定的源。
问题2) 当您找到每个节点时,将它们推入一个集合,这意味着您可以通过动态询问正在构建的集合,很容易地查看是否在某个点上“返回”。
问题3) 如果在任何时候你看到你正在折回,你可以从集合中弹出东西并“后退”。然后从这一点开始,再次尝试“前进”。
黑客:如果你正在使用Sql Server 2008,有一些新的“层次结构”的东西,你可以用它来快速解决这个问题,如果你把你的数据结构成树状。
我在搜索中找到了这个页面,由于循环与强连接组件不相同,我继续搜索,最后,我找到了一个高效的算法,它列出了有向图的所有(基本)循环。这篇论文来自唐纳德·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的算法是最快的。
深度优先搜索和回溯应该在这里工作。 保存一个布尔值数组,以跟踪您以前是否访问过某个节点。如果您没有新节点可访问(不涉及已经访问过的节点),那么只需返回并尝试不同的分支。
如果你有一个邻接表来表示图,DFS很容易实现。例如adj[A] = {B,C}表示B和C是A的子结点。
例如,下面的伪代码。“start”是开始的节点。
dfs(adj,node,visited):
if (visited[node]):
if (node == start):
"found a path"
return;
visited[node]=YES;
for child in adj[node]:
dfs(adj,child,visited)
visited[node]=NO;
用开始节点调用上面的函数:
visited = {}
dfs(adj,start,visited)
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();
}
从开始节点s开始的DFS,在遍历过程中跟踪DFS路径,如果在到s的路径中发现从节点v开始的边,则记录该路径。(v,s)是DFS树中的后边,因此表示包含s的周期。