Написание 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

Let 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