Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Программа 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.3 представляет собой другой пример использования класса итератора в АТД графов для распечатки таблиц вершин, смежных с каждой конкретной вершиной, как показано на рис. 17.7. Программные коды этих двух примеров во многом подобны, как они подобны программным реализациям многочисленных алгоритмов обработки графов. Следует отметить тот замечательный факт, что мы можем построить все алгоритмы, изучаемые в данной книге, на основе абстракции обработки всех вершин, смежных с каждой конкретной вершиной (что эквивалентно обработке всех ребер в графе), как и в указанных выше функциях.
|