Глава 18. Поиск на графе. ну графа и одно ребро дерева — на каждое ребро графа

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

Свойство 18.10. Для любого узла w в дереве BFS с корнем в вершине v путь из v в w со­ответствует кратчайшему пути из v в w в соответствующем графе.

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

Программа 18.8. Поиск в ширину_____________________________________________

Данный класс поиска на графе посещает вершину на основании просмотра инцидентных ей ребер, помещая все ребра, ведущие на непосещенную вершину, в очередь вершин, планируемых для просмотра. Вершины маркируются в порядке их посещения вектором ord. Функция search, вызываемая конструктором, выполняет построение явного представления дерева BFS с родительскими связями (ребра, которые приводят нас на каждый узел в первый раз) в другом векторе st, который затем может быть использован для решения базовой задачи поиска кратчайшего пути (см. текст).

#include " QUEUE.cc"

template < class Graph>

class BFS: public SEARCH< Graph>

{ vector< int> st;

void searchC(Edge e) { QUEUE< Edge> Q; Q.put(e);

while OQ.emptyO) if (ord[(e = Q.get()).w] == -1) { int v = e.v, w = e.w; ord[w] = cnt++; st[w] = v; typename Graph:: adjIterator A(G, w); for (int t = A.beg();! A.end(); t = A.nxt())

if (ord[t] == -1) Q.put (Edge (w, t)); } > public:

BFS(Graph & G): SEARCH< Graph> (G), st(G.V(), -1)

{ search(); }

int ST(int v) const { return st[v]; } >;

Программа 18.9. Усовершенствованный алгоритм BFS__________________________

Чтобы в очереди, которая используется во время выполнения BFS, было не более V мест, мы маркируем вершины в момент постановки их в очередь.

void searchC(Edge e) { QUEUE< Edge> Q;

Q.put(e); ord[e.w] = cnt++;