用迭代深化编写DFS而无需递归 [英] Writing a DFS with iterative deepening without recursion

问题描述

因此，目前我有一个DFS，伪码如下：

pre code> procedure DFS（图形，源代码）：
create一个堆栈S
将源压入S
标记源
，同时S不为空：
从S中弹出一个项目到v
为每个边缘发生事件v in图：
如果w未标记，则让w为e
的另一端：
mark w
将w推到S

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

解决方案

为图的每个节点设置 Node 结构，添加名为 level 的字段，然后：

  procedure DFS（图形，源代码，深度）：
创建堆栈S 
 source.level = 0 
 push源到S 
标记源
而S不为空时：
从S中弹出一个项目到v 
 if v.level>深度
继续
 
对于每个边e事件在图中：
如果w未标记，则让w为e 
的另一端：
标记w 
 w.level = v.level + 1 
将w推入S 
  

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?

解决方案

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屋！