Как отследить глубину в этом объекте графа алгоритм поиска в глубину?

Question

У меня есть этот код, который перебирает дерево, выполняя поиск в глубину.Каждый элемент решается ровно один раз.Очень хорошо.

-(void)iterateOverTree:(TreeNode *)node
{
    NSMutableArray * elements = [NSMutableArray array];
    [elements addObject:node];

    while([elements count])
    {
        TreeNode * current = [elements objectAtIndex:0];
        [self doStuffWithNode:current];
        for(TreeNode * child in current.children)
        {
            [elements addObject:child];
        }

        [elements removeLastObject];
    }
}

НО: Как я могу отслеживать текущую глубину на графике?Мне нужно знать уровень глубины.Так, например, у меня есть эти узлы:

A имеет дочерние элементы B, J. B имеет дочерние элементы C. C имеет дочерние элементы D. D имеет дочерние элементы E, F, I.

Когда A находится вуровень глубины 1, тогда B равен 2, а C равен 3.

С помощью рекурсии было очень легко отслеживать текущий уровень глубины.Просто вставьте переменную в переменную перед вызовом себя и уменьшите ее после вызова самой себя.

Но здесь с этим причудливым циклом while это невозможно.В блоке нет блока в блоке, как в случае с рекурсией.

На самом деле я не хочу добавлять свойства (или переменные экземпляра) к объекту TreeNode, так как его следует повторно использовать вуниверсальный способ для любого вида графов объектов.

У кого-нибудь есть идеи, как это сделать?Нужно ли вводить другой массив для отслеживания посещенных узлов?

Answer 1

Я думаю, вам также нужно сложить глубины.Это то, что вы на самом деле сделали бы, если бы у вас была рекурсивная версия.Просто хранилище было бы «невидимым», поскольку вы бы использовали стек вызовов вместо явного стека, как вы делаете сейчас.

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

Обновление:

Вы должны быть в состоянии сделатьDFS без стека вообще, если вместо этого вы будете следовать родительским указателям узла для резервного копирования дерева.Это сделало бы поддержание глубины простым.Но вы должны быть осторожны, чтобы не нарушать сложность наихудшего случая с линейным временем, повторно сканируя детей, чтобы выяснить, где вы были.

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

Кстати, внимательно посмотрев на ваш алгоритм,Разве вы не смотрите на ту сторону массива, когда получаете следующий текущий узел?Это должно работать так:

push root
while stack not empty:
   current = pop
   push all children of current

Answer 2

Я верю, что вы на самом деле делаете BFS. Вы работаете со списками. Для выполнения DFS вы должны использовать стек;

Это может быть полезно для трека глубины, вы можете посмотреть на вектор p (родителей)

Answer 3

Я не понимаю вашу нотацию, но если я правильно прочитал, вы обрабатываете узел и добавляете всех детей в свой список дел.

Если бы вы могли изменить эту часть на использование рекурсии, вы могли бы отслеживать глубину дерева, поскольку это будет глубина рекурсии.

Таким образом, вместо добавления дочернего узла, выполняйте рекурсию для каждого дочернего узла.

НТН

Mario

Answer 4

Предположим, что вы выполняете BFS, проще всего ввести еще одну очередь для глубины, которая отражает очередь ваших узлов. Инициализируйте глубину до нуля. Каждый раз, когда вы нажимаете на очередь узлов, нажмите текущую глубину + 1 в очередь глубины.