我怎样才能在图中找到所有'长'简单的非循环路径？ [英] How can I find all 'long' simple acyclic paths in a graph?

问题描述

假设我们有一个完全连接的有向图 G 。顶点是 [a，b，c] 。每个顶点之间在两个方向上都有边。

给定起始顶点 a ，我想遍历只有当我点击一个已经在路径中的顶点时才保存路径。
$ b

因此，函数 full_paths（a， G）应返回：

   -  [{a，b}，{b，c}， {c，d}] 
  -  [{a，b}，{b，d}，{d，c}] 
  -  [{a，c}，{c，b}，{b ，d}] 
  -  [{a，c}，{c，d}，{d，b}] 
  -  [{a，d}，{d，c}，{c，b }] 
  -  [{a，d}，{d，b}，{b，c}] 
  

我不需要像'code> [{a，b}] 或 [{a，b}，{b ，c}] ，因为它已包含在第一个结果中。

除了生成powerset之外，还有其他方法可以完成它的G和过滤出一定大小的结果？

我该如何计算这个值？

编辑：正如Ethan指出的那样，这可以通过深度优先搜索方法解决，但不幸最近我不明白如何修改它，使它在回溯之前存储路径（我使用Ruby Gratr 实现我的算法）

解决方案

href =http://en.wikipedia.org/wiki/Depth-first_search =nofollow>深度优先搜索或某些变体？深度优先搜索尽可能遍历，然后回溯。每次需要回溯时，您都可以记录路径。

Let's say we have a fully connected directed graph G. The vertices are [a,b,c]. There are edges in both directions between each vertex.

Given a starting vertex a, I would like to traverse the graph in all directions and save the path only when I hit a vertex which is already in the path.

So, the function full_paths(a,G) should return:

- [{a,b}, {b,c}, {c,d}]
- [{a,b}, {b,d}, {d,c}]
- [{a,c}, {c,b}, {b,d}]
- [{a,c}, {c,d}, {d,b}]
- [{a,d}, {d,c}, {c,b}]
- [{a,d}, {d,b}, {b,c}]

I do not need 'incomplete' results like [{a,b}] or [{a,b}, {b,c}], because it is contained in the first result already.

Is there any other way to do it except of generating a powerset of G and filtering out results of certain size?

How can I calculate this?

Edit: As Ethan pointed out, this could be solved with depth-first search method, but unfortunately I do not understand how to modify it, making it store a path before it backtracks (I use Ruby Gratr to implement my algorithm)

解决方案

Have you looked into depth first search or some variation? A depth first search traverses as far as possible and then backtracks. You can record the path each time you need to backtrack.

这篇关于我怎样才能在图中找到所有'长'简单的非循环路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！