Поиск

Поиск в ширину

Определение:

• Поиск в ширину — это алгоритм, ищущий по дереву (или графу), просматривая по уровням начиная с корня.

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

Особенности:

• Поиск в ширину оптимален для поиска по дереву, чья ширина превышает глубину.

• Во время хождения по дереву, алгоритм сохраняет информацию о нём в очереди.

  • В связи с использованием очереди такой метод поиска потребляет больше памяти, чем поиск в глубину.
  • Очередь использует память для хранения указателей.

Эффективность («О» большое):

• Поиск: поиск в ширину — O(|E| + |V|).
• E — количество рёбер (граней?).
• V — количество вершин.

Поиск в глубину

Определение:

• Поиск в глубину — это алгоритм, ищущий по дереву (или графу) сначала в глубину начиная с корня.

  • Алгоритм идёт по дереву, переходя между уровнями по левым дочерним узлам, пока не дойдёт до самого низа.
  • Завершив проход по ветви, алгоритм возвращается обратно, просматривая правые дочерние узлы этой ветви. Причём, если возможно, выбирает самые левые из узлов, расположенных справа от предыдущего маршрута.
  • Завершив просмотр всей ветви, алгоритм переходит к узлу, расположенному справа от корня, и снова идёт по левым дочерним узлам до самого дна.
  • Последним анализируется крайний правый узел (расположенный справа от всех своих предшественников).

Особенности:

• Алгоритм оптимален для поиска по дереву, чья глубина превышает ширину.

• Для работы алгоритма используется стек.

  • Поскольку стек является LIFO-структурой, ему не нужно отслеживать указатели узлов, поэтому потребляется меньше памяти, чем в случае с поиском в ширину.
  • Когда алгоритм не может дальше идти по левой стороне, он начинает анализировать стек.

Эффективность («О» большое):

• Поиск: поиск в глубину — O(|E| + |V|).
• E — количество рёбер (граней?).
• V — количество вершин.

Сравнение поисков в ширину и в глубину

• Выбирайте тип поиска в соответствии с размером и формой дерева.

  • Для широких, мелких деревьев используйте поиск в ширину.
  • Для глубоких, узких деревьев используйте поиск в глубину.

Нюансы:

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