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

1.2.1 Обход в ширину

1.2.1.1 Метод обхода

Обход в ширину (breadth-first traversal) является основой для многих важных алгоритмов для работы с графами.

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

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

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

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

Ниже представлен псевдокод алгоритма поиска в ширину.

Таблица 1.2 – Псевдокод обхода в ширину.

[1] 1.2.1.3 Анализ обхода

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

1.2.1.4. Корректность

Утверждение: В алгоритме поиска в ширину очередь всегда содержит сначала некоторое количество вершин с расстоянием ,а потом некоторое количество вершин с расстоянием (возможно, нулевое).

▲ Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

База: изначально очередь содержит только одну вершину с расстоянием 0, утверждение верно.

Переход: пусть после l-го шага алгоритма очередь содержит p вершин с расстоянием и вершин с расстоянием . Тогда на шаге мы извлечем из очереди одну вершину и добавим в нее все не посещенные вершин связанные с ней; расстояние до них, очевидно, будет равно . У нас останется (возможно, 0) вершин с расстоянием и вершин с расстоянием , что соответствует нашему инварианту. ■

Теорема: Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.

▲ Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина , и она имеет своим предком в дереве обхода в ширину , а предок в кратчайшем пути до – вершина . Так как w – предок u в кратчайшем пути, то и расстояние до найдено верно, Так как предок в дереве обхода в ширину, то Расстояние до найдено некорректно, поэтому Подставляя сюда два последних равенства, получаем то есть, . Из ранее доказанной леммы следует, что в этом случае вершина попала в очередь и была обработана раньше, чем . Но она соединена с , значит, не может быть предком в дереве обхода в ширину. Мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.[4]