![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 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]; } >;
Чтобы в очереди, которая используется во время выполнения BFS, было не более V мест, мы маркируем вершины в момент постановки их в очередь. void searchC(Edge e) { QUEUE< Edge> Q; Q.put(e); ord[e.w] = cnt++;
|