algorithm - 枚举无向/未加权图的节点集

Question

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

这个问题类似于这个one ;有这个区别:对于 n=3；我还需要找到路径:A-B-C 和 C-E-F。

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

A-B-C-D

A-B-C-E

A-B-C-F

A-C-E-F

我想这是一个类似的问题； “所有对 - 所有路径”，其中每条路径最多可以包含 n 个节点。能否请您也介绍一下这些方法的计算复杂度？

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

Answer 1

您基本上可以将 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

另一个(效率较低，但可能更优雅)正在做 Iterative Deepening DFS , length=1,2,...,n(并且仅将打印放在停止子句中)