如何找到所有' long'图中的简单非循环路径? [英] How can I find all 'long' simple acyclic paths in a graph?

问题描述

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

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.

给出一个起始顶点 a ，我想在所有方向上遍历该图，并仅在碰到路径中已经存在的顶点时才保存路径.

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.

因此，函数 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}]

我不需要 [{{a，b}] 或 [{a，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.

除了生成G的幂集并过滤出一定大小的结果之外，还有其他方法吗?

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

我该如何计算?

编辑:正如Ethan所指出的那样，可以通过深度优先搜索方法解决此问题，但是不幸的是，我不知道如何修改它，因此它会在回溯之前存储路径(我使用Ruby Gratr 来实现我的算法)

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.

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