Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Программа 17.2. Пример клиентской функции обработки графов
|
|
Эта функция осуществляет один из способов использования АТД графа с целью реализации базовой операции обработки графов, в некотором смысле независимой от представления. Она возвращает все ребра графа в виде вектора.
Эта реализация служит иллюстрацией основы большинства программ, которые мы будем рассматривать: мы производим обработку каждого ребра графа путем проверки всех вершин, смежных с каждой конкретной вершиной. В общем случае мы не вызываем функции beg, end и nxt никаким другим способом кроме того, который используется в этой программе, и это обстоятельство позволяет лучше оценить рабочие характеристики нашей реализации (см. раздел 17.5).
Часть 5. Алгоритмы на графах
template < class Graph> vector < Edge> edges(Graph & G) { int E = 0; vector < Edge> a(G.E()); for (int v = 0; v < G.V(); v++) {
typename Graph:: adjIterator A(G, v); for (int w = A.begO;! A.end(); w = A.nxt()) if (G.directed() | | v < w)
|
a[E++] = Edge(v, w); }
return a; }
| РИСУНОК 17.7. ФОРМАТ СПИСКА СМЕЖНЫХ ВЕРШИН Эта таблица служит еще одним способом представления графа, приведенного на рис. 17.1; мы связываем каждую вершину с множеством смежных с ней вершин (которые соединены с ней посредством одного ребра). Каждое ребро фигурирует в двух множествах: для каждого ребра u-v графа вершина и содержится в множестве, соответствующем вершине v, а вершина v содержится в множестве, соответствующем вершине и. |
Программа 17.3 представляет собой другой пример использования класса итератора в АТД графов для распечатки таблиц вершин, смежных с каждой конкретной вершиной, как показано на рис. 17.7. Программные коды этих двух примеров во многом подобны, как они подобны программным реализациям многочисленных алгоритмов обработки графов. Следует отметить тот замечательный факт, что мы можем построить все алгоритмы, изучаемые в данной книге, на основе абстракции обработки всех вершин, смежных с каждой конкретной вершиной (что эквивалентно обработке всех ребер в графе), как и в указанных выше функциях.