图上DFS的非递归方法

Question

我正在做运动，我有点困了，需要一些帮助。假设有向图上有以下顶点和边：AB、BC、AD、CD、DC、DE、CE、EB、AE，如下所示

到目前为止，我已经设法通过使用DFS和递归来解决这个问题。我跟踪深度（即距离源有多少边），当深度超过3时，递归函数返回。

我现在想做的是不使用递归来解决它，也就是说，使用堆栈，但我卡住了！如果我使用以下类似的东西（伪代码）：

s.create() <- create stack
s.push(nodeA)
depth = 0

while !s.empty
  n = s.pop()

  foreach (n.connectedVertices as c)
    s.push(c)
  depth++

那么我就无法知道每个顶点应该在哪个深度。我一直在考虑以某种方式使用一堆堆栈（为每个深度保存？）但我还没弄明白。

任何帮助都将不胜感激。

Answer 1

可以通过在堆栈中推动对来实现这一点
该对将包含（节点、深度）
现在开始推送（节点，0）。

s.create()
s.push(nodeA , 0)

while !s.empty
    cur_node , depth = s.pop()  
    if depth==3
        continue // if depth = 3 then we don't need to push anything .

    for each node connected with cur_node
        s.push(node , depth + 1)

我希望你知道我们如何计算答案。