Complete Iterative Deepening Depth First Search

Question

At the minute I have an object that looks a bit like this.

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

And I'm trying to convert it into another object that looks pretty similar apart from the fact that it doesn't allow loops.

It should handle loops by not expanding the children of nodes that have already appeared at a higher depth. Iterative deepening solves this (depth first search implementation but breadth first search order) but I'm struggling with an implementation using the following structure.

All implementations I found rely on finding some sort of goal node, whereas I need the whole tree expanded.

Any help would be appreciated. :D

Answer 1

Add a Dictionary<Step, int> and each time you expand a node, add it with its depth.

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