1

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

给定一个起始 vertex 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}]or这样的“不完整”结果[{a,b}, {b,c}]，因为它已经包含在第一个结果中。

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

我该如何计算？

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

4

2 回答 2

1

您是否研究过深度优先搜索或一些变化？深度优先搜索尽可能地遍历然后回溯。您可以在每次需要回溯时记录路径。

于 2011-11-11T19:14:45.620 回答
1

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

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是 graph 的顶点列表G。

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

于 2011-11-12T13:31:30.023 回答