DFS на графе нерекурсивным способом

Question

Я работаю над упражнением и застрял, мне нужна помощь. Предположим, у нас есть следующие вершины и ребра на ориентированном графе: AB, BC, AD, CD, DC, DE, CE, EB, AE, изображенные ниже

Попытка изобразитьсколько "поездок" существует от C до C, не более 3 ребер. Это будет два (2), CDC и CEBC

. Пока мне удалось решить эту проблему с помощью 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)

Надеюсь, вы поняли, как мы можем рассчитать ответ.