我如何才能找到(遍历)有向图中从/到给定节点的所有周期?

例如,我想要这样的东西:

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的算法是最快的。

其他回答

http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf

深度优先搜索和回溯应该在这里工作。 保存一个布尔值数组,以跟踪您以前是否访问过某个节点。如果您没有新节点可访问(不涉及已经访问过的节点),那么只需返回并尝试不同的分支。

如果你有一个邻接表来表示图,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)

我曾经在面试中遇到过这样的问题,我怀疑你遇到过这种情况,你来这里寻求帮助。把这个问题分解成三个问题就容易多了。

如何确定下一个有效点 路线 你如何确定一个点是否存在 被使用 你如何避免越过 同样的观点

问题1) 使用迭代器模式提供迭代路由结果的方法。放置获取下一个路由的逻辑的一个好地方可能是迭代器的“moveNext”。要找到有效的路由,这取决于您的数据结构。对我来说,这是一个sql表充满有效的路由可能性,所以我必须建立一个查询,以获得有效的目的地给定的源。

问题2) 当您找到每个节点时,将它们推入一个集合,这意味着您可以通过动态询问正在构建的集合,很容易地查看是否在某个点上“返回”。

问题3) 如果在任何时候你看到你正在折回,你可以从集合中弹出东西并“后退”。然后从这一点开始,再次尝试“前进”。

黑客:如果你正在使用Sql Server 2008,有一些新的“层次结构”的东西,你可以用它来快速解决这个问题,如果你把你的数据结构成树状。

从节点X开始,检查所有子节点(如果无方向,父节点和子节点是等价的)。将这些子节点标记为X的子节点。对于任何这样的子节点A,标记它的子节点是A的子节点,X',其中X'标记为2步远。)如果您稍后点击X并将其标记为X的子节点”,这意味着X处于3节点周期中。回溯到它的父节点很容易(因为算法不支持这一点,所以你可以找到任何一个有X'的父节点)。

注意:如果图是无向的或者有任何双向边,这个算法会变得更复杂,假设你不想在一个周期内两次遍历同一条边。

我在搜索中找到了这个页面,由于循环与强连接组件不相同,我继续搜索,最后,我找到了一个高效的算法,它列出了有向图的所有(基本)循环。这篇论文来自唐纳德·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的算法是最快的。