Структуры и алгоритмы компьютерной обработки данных (стр. 8 )

(А) Все вершины из будут посещены после всех вершин из , .

Строгое доказательство легко провести индукцией по . Отметим еще следующий факт.

(Б) Если активной является вершина из , то в этот момент все вершины из уже посещены.

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

Рассмотрим теперь момент работы алгоритма, когда активной является вершина и обнаруживается смежная с ней новая вершина . В BFS-дереве расстояние между и на 1 больше, чем расстояние между и . В графе расстояние между и не больше, чем , так как и смежны. Ввиду (А) это расстояние не может быть меньше , а ввиду (Б) оно не может быть равно . Значит, , т. е. в графе расстояние между и тоже на 1 больше, чем расстояние между и . Следовательно, если до какого-то момента работы алгоритма расстояния от каждой из посещенных вершин до стартовой вершины в графе и в дереве были равны, то это будет верно и для вновь посещаемой вершины. Поскольку это верно вначале, когда имеется единственная посещенная вершина (оба расстояния равны ), то это останется верным и тогда, когда будут посещены все вершины.

Итак, мы можем применить поиск в ширину для вычисления расстояний от стартовой вершины до всех остальных вершин графа - нужно только в процессе обхода для каждой посещаемой вершины определять расстояние от до в BFS-дереве. Это сделать легко: , где - активная вершина. Вначале устанавливаем .

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

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

Модифицируя процедуру BFS с учетом сделанных замечаний, получаем следующий алгоритм:

Алгоритм 2.Построение BFS-дерева и вычисление расстояний от вершины до всех остальных вершин:

for do while do for do if then

Процедура поиска в глубину

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

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

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