1

在无向和无权图上，如何枚举所有长度为 1,2,..,n 的连接节点组（n 是用户定义的值）？

这个问题与这个问题相似；有这个区别：对于n = 3；我还需要找到路径：ABC 和 CEF。

如果 n 为 4，则路径还应包括：

A B C D

ABCE

ABCF

ACEF

我想这是一个类似的问题；“所有对 - 所有路径”，其中每条路径最多可以包含 n 个节点。您还可以告诉方法计算复杂度吗？

我的想法是我需要同时使用DFS和BFS，但我不确定这是否有效？

4

1 回答 1

0

您基本上可以将 DFS 与一个额外的变量一起使用，该变量通过 的递归传递length，在每次迭代时都会减少。停止条件将是这个额外变量达到 0 时。

类似于以下内容：

DFS(source,length,path):
   print path //this is always done, because we want all paths up to n
   if (length == 0): //stop clause
      return
   for each (source,u) is an edge:
       path.append(u)
       DFS(u,length-1,path)
       path.removeLast() //clean up environment

另一个（效率较低，但可能更优雅）是进行迭代深化 DFS，长度=1,2,...,n （并将打印仅放在停止子句中）

于 2013-01-09T14:48:13.910 回答