Завершите итеративное углубление глубины Первый поиск

Question

В тот момент, когда у меня есть объект, который выглядит примерно так.

C#
public class Step {
  int id;
  List<Step> nextSteps;
}

И я пытаюсь преобразовать его в другой объект, который выглядит довольно похоже, за исключением того факта, что он не допускает циклы.

Он должен обрабатывать циклы, не расширяя дочерние узлы узлов, которые уже появились на глубине выше . Итеративное углубление решает эту проблему (реализация поиска в глубину, но в порядке поиска в ширину), но я борюсь с реализацией, использующей следующую структуру.

Все реализации, которые я нашел, основаны на поиске какого-то целевого узла, тогда как мне нужно, чтобы все дерево было расширено.

Любая помощь будет оценена. : D

Answer 1

Добавьте Dictionary<Step, int> и каждый раз, когда вы расширяете узел, добавляйте его с глубиной.

void ExpandStep(Step s, int d)
{
    int prevDepth;
    if (lookup.TryGetValue(s, out prevDepth) && prevDepth <= d)
      return;
    lookup.Add(s, d);
    ... 
}