编写一个没有递归的迭代深化的 DFS [英] Writing a DFS with iterative deepening without recursion

问题描述

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

So currently i have a DFS with the following pseudocode

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

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

How do I alter this function to accept a third argument that limits the depth of the search?

推荐答案

让 Node 为图的每个节点创建一个结构，添加一个名为 level 的字段，然后:

Let Node a structure for each node of the graph, add a field called level and then:

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

这篇关于编写一个没有递归的迭代深化的 DFS的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！