图形上的DFS非递归方式

Question

我正在锻炼身体，有点卡住，需要帮助。假设我们在有向图上具有以下顶点和边：AB，BC，AD，CD，DC，DE，CE，EB，AE如下图所示

试图找出从C到C有多少个“行程”，边不超过3个。那将是两（2），C-D-C和C-E-B-C

到目前为止，我已经设法通过使用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

您可以通过将对压入堆栈来完成。该对将包含（node，depth）。现在最初推送（node，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)

我希望您对如何计算答案有了想法。