Алгоритмы обхода графа

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

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

В.Липский называет метод поиска "хорошим", если

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

В данном разделе представлен алгоритм обхода графа, который называется поиском в ширину (Breadth First Search), и соответствующее этому алгоритму дерево. Об этом говорит сайт https://intellect.icu . Также представлен алгоритм поиска в глубину(Depth First Search) и доказываются некоторые свойства этого вида обхода графа.

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

Стратегии поиска вершины на графе. 
(серым отмечены использованные во время поиска вершины ребра)