итеративное удлинение псевдокода для обхода всех узлов

Question

Каков будет алгоритм, псевдокод или реальный код для прохождения всех узлов в графе с использованием итеративного подхода с углублением в глубину?

Answer 1

Сначала я даю псевдокод глубины для графа

DLS(node, goal, depth, visited) 
{
  if ( depth >= 0 ) 
    {
    if ( node == goal )
      return node

    visited.insert(node)

    for each child in expand(node)
      if (child is not in visited)
          DLS(child, goal, depth-1, visited)
  }
}

, а итеративный DLS равен

IDDFS(start, goal)
{
  depth = 0
  while(no solution)
  {
    visited = [] // <-- Empty List
    solution = DLS(start, goal, depth,visited)
    depth = depth + 1
  }
  return solution
}

. Вы всегда можете преобразовать граф в дерево, удаливграфическая петля с посещенным списком .:)