Часть 5, Алгоритмы на графах. Поиск в ширину полностью покрывает область, прилегающую к исходной точке, уда­ляясь от нее только после того

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

Главное, что требуется для правильного понимания алгоритмов обработки графов, зак­лючается в том, чтобы четко представлять себе, что не только различные стратегии поиска служат эффективным средством изучения тех или иных свойств графа, но и то, что мно­гие из них можно реализовать стандартным путем. Например, поиск в ширину, показан­ный на рис. 18.13, свидетельствует о том, что в рассматриваемом графе присутствует длинный путь, а поиск в ширину, изображенный на рис. 18.24, говорит о том, что в рас­сматриваемом графе имеется множество коротких путей. Несмотря на отмеченные раз­личия в динамике, поиски в глубину и ширину имеют много общего; основное отличие между ними заключается лишь в структуре данных, которая используется для сохранения еще не исследованных ребер (и в чисто случайном совпадении, которое заключается в том, что мы можем использовать рекурсивную реализацию поиска в ширину, при этом неявную поддержку стека обеспечивает сама система). Теперь мы обратимся к изучению обобщенных алгоритмов поиска на графах, которые охватывают поиск в глубину, поиск в ширину и множество других полезных стратегий, и могут послужить основой для ре­шения разнообразных классических задач обработки графов.