无需递归即可编写迭代深化的 DFS

Question

所以目前我有一个具有以下伪代码的 DFS

procedure DFS(Graph,source):
      create a stack S
      push source onto S
      mark source
      while S is not empty:
          pop an item from S into v
          for each edge e incident on v in Graph:
              let w be the other end of e
              if w is not marked:
                 mark w
                 push w onto S

如何更改此函数以接受限制搜索深度的第三个参数？

Answer 1

令 Node 为图的每个节点的结构，添加一个名为 level 的字段，然后按如下方式处理图：

procedure DFS(Graph,source, depth):
  create a stack S
  source.level = 0
  push source onto S
  mark source
  while S is not empty:
      pop an item from S into v
      if v.level > depth
        continue

      for each edge e incident on v in Graph:
          let w be the other end of e
          if w is not marked:
             mark w
             w.level = v.level + 1
             push w onto S

Answer 2

1. 当找到对象时，该过程将返回成功。
2. 当找到一个对象时，S 将包含路径 [root, source) 中的节点。 （不包括源本身。）

---

procedure DFS(Graph, source, depth):
    StackInit(S)
    if source is goal then
        return success
    markVisited(source)
    S.push(null, source)              // S is a close-list
    while S is not empty then do
        c, p := S.pop()
        r := next(c, p)               // return the next sibling of c
        if r is null then
            continue
        S.push(r, p)
        if r is marked visited then   // that already marked means it cannot be goal
            continue
        if r is goal then
            return success
        markVisited(r)
        if equal(depth(r), depth) then // here is what OP wants.
            continue
        S.push(null, r)

return fail