我怎样才能找到所有“长”的东西？图中的简单非循环路径？

Question

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

给定一个起始顶点a，我想在所有方向上遍历图形，并仅当我遇到路径中已经存在的顶点时才保存路径。

因此，函数 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}]，因为它已经包含在第一个结果中。

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

我该如何计算这个？

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

Answer 1

您是否研究过深度优先搜索或其他变体？深度优先搜索会遍历尽可能远的距离，然后回溯。每次需要回溯时都可以记录路径。

Answer 2

如果您知道图 G 是完全连通的，则当 N 时，有 N! 条长度为 N 的路径 是图 G 中的顶点数。您可以通过这种方式轻松计算它。您有 N 种选择起点的可能性，那么对于每个起点，您可以选择 N-1 个顶点作为路径上的第二个顶点，依此类推，当您只能选择最后一个时每条路径上未访问过的顶点。所以你有 N*(N-1)...*2*1 = N! 条可能的路径。当您无法选择起点（即给出）时，它与在具有 N-1 顶点的图 G' 中查找路径相同。所有可能的路径都是所有顶点集的排列，即在您的情况下是除起点之外的所有顶点。当您有排列时，您可以通过以下方式生成路径：

perm_to_path([A|[B|_]=T]) -> [{A,B}|perm_to_path(T)];
perm_to_path(_) -> [].

在您的情况下，如何生成排列的最简单方法是

permutations([]) -> [];
permutations(L) ->
  [[H|T] || H <- L, T <- permutations(L--[H])].

：

paths(A, GV) -> [perm_to_path([A|P]) || P <- permutations(GV--[A])].

其中 GV 是图 G 的顶点列表强>。

如果您想要更高效的版本，则需要更多的技巧。