边数有界的未加权无向图中两结点间的所有路

Question

我有一个未加权有向图G，它可能非常大（数千个节点）。

Answer 1

您可以修改dfs来解决此问题。只需添加另一个参数-当前的深度，然后如果在target nodetarget之前达到路径长度限制，则剪切dfs。为了演示这个想法，我将使用递归实现，并使用一个全局数组used--在此过程中访问的节点。另外，我将假设我们已经使用邻域列表表示来存储该图（让我们将其称为nelist，节点v的邻域位于nelist[v]):

used[n] = {false}
neList; // neighborhoodList
limit = 10 // max path len
void dfs(int v, int depth) {
  if (depth == limit) {
    if (v == target) {
       print_path
    } else {
       return
    }
  }
  for u in neList[v] {
    if (used[u]) {
      continue;
    }
    used[u] = true
    dfs(u, depth + 1)
    used[u] = false
  }
}

您可以对此方法进行优化，首先从目标节点执行bfs，以计算target和所有节点之间的min_distance。在DFS中，如果dept+min_dist[u]<=limit，则只转到邻居u。