![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Функции АТД поиска на графе
Поиск в глубину и другие методы поиска на графах, которые будут рассматриваться позже в этой главе, предусматривают перемещение по ребрам графа при переходе от вершины к вершине с целью систематического обхода каждой вершины и каждого ребра графа. Однако переход от вершины к вершине вдоль ребер может провести через все вершины только в рамках одной и той же связной компоненты, которой принадлежит исходная вершина. Разумеется, в общем случае графы не обязательно должны быть связными, следовательно, мы должны вызывать функцию поиска для каждой связной компоненты. Обычно мы используем функции поиска на графе, которые, пока все вершины графа не будут помечены как посещенные, выполняют следующие действия: ■ Найти непомеченную вершину (отправная вершина). ■ Посетить (и пометить как посещенные) все вершины в связной компоненте, ко Часть 5. Алгоритмы на графах
Программа 18.2. Поиск на графе___________________________________________ Данный базовый класс предназначен для обработки графов, которые могут оказаться несвязными. Производные классы должны дать определение функции searchC, которая, будучи вызванной с петлей вершины v в качестве второго аргумента, устанавливает ord[t] в cnt++ для каждой вершины t, содержащейся в той же связной компоненте, что и вершина v. Чаще всего конструкторы в производных классах вызывают функцию search, которая, в свою очередь, вызывает searchC один раз для каждой связной компоненты графа. template < class Graph> class SEARCH { protected: const Graph & G; int cnt; vector < int> ord; virtual void searchC(Edge) = 0; void search() { for (int v = 0; v < G.V(); v++) if (ord[vj == -1) searchC (Edge (v, v)); } public: SEARCH (const Graph & G): G(G), ord(G.V(), -1), cnt(0) { } int operator[](int v) const { return ord[v]; } };
Программа 18.2 представляет собой реализацию, которая служит иллюстрацией этих возможностей. На рис. 18.8 представлен пример, который показывает, как отражается посещение каждой вершины на состоянии вектора ord любого производного класса. Как правило, рассматриваемые производные классы также исследуют все ребра, инцидентные каждой посещенной вершине. В таких случаях знание того факта, что мы посетили все вершины, говорит нам, что мы также посетили все ребра, как и в случае обхода Тремо. Глава 18. Поиск на графе
Программа 18.3 представляет собой пример, который показывает, как можно получить базовый класс DFS для вычисления остовного леса на основе базового класса SEARCH из программы 18.2. Мы включаем приватный вектор st в производный класс с целью хранения представления дерева в виде родительских связей, которое мы инициализируем в конструкторе. Кроме того, мы даем определение функции searchC, которая во всем совпадает с функцией searchC из программы 18.1 за исключением того, что она принимает ребро v-w в качестве аргумента и устанавливает st[w] в v. Наконец, мы вводим общедоступную функцию-элемент, которая дает клиентам возможность определять родителя любой вершины. Остовные леса являются предметом интереса для многих приложений, но в этой главе они интересуют нас главным образом в силу того, что они важны для понимания динамического поведения поиска в глубину, что является темой обсуждений раздела 18.4. В связном графе конструктор из программы 18.2 вызывает функцию searchC всего один раз, а именно, для ребра 0-0, после чего выясняет, что все другие вершины помечены. В графе, состоящем из более чем одной связной компоненты, конструктор просматривает все связные компоненты непосредственно. Поиск в глубину является первым из нескольких методов, который будет применяться для просмотра связной компоненты графа. Независимо от того, какой метод (при этом не играет роли, каково представление графа) был выбран, программа 18.2 является эффективным методом просмотра всех вершин графа.
|