Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Сравнение реализаций
|
|
Постановка задачи
Была поставлена задача реализовать алгоритм поиска в ширину и сравнить свою реализацию с реализацией этого алгоритма в библиотеке Boost Graph Library. Boost Graph Library (BGL) предоставляет гибкую и эффективную реализацию концепции графов. В данной библиотеке можно выбрать представление графа (например, список смежности или матрица смежности), тип и алгоритм из большого набора алгоритмов, среди которых имеется алгоритм поиска в ширину.
Описание алгоритма
Поиск в ширину (BFS, Breadth-first search) — метод обхода и разметки вершин графа
Этот алгоритм делает следующее:
1. Добавляет начальную вершину в очередь и помечает её как использованную.
2. Извлекает следующую вершину из очереди и добавляет в очередь смежные ей неиспользованные вершины, помечая их как использованные.
3. Если очередь непуста, переходит к пункту 2.
Алгоритм называется поиском в ширину, так как поиск идет вширь: сначала выбираются все соседние для заданной вершины s, затем соседи соседей и так далее.
| void Graph:: BFSearch(int v) { queue< int> q; bool* mark; mark = new bool [NumVertex]; for (int i = 0; i < NumVertex; i++) mark[i] = false; q.push(v); mark[v] = true; while (! q.empty()) { int t; t = q.front(); q.pop(); cout < < t < < " "; for (int i = 0; i < NumVertex; i++) if (mat[t][i]! = 0 & &! mark[i]) { q.push(i); mark[i] = true; } } } Рис. 1 Исходный код алгоритма поиска в ширину |
Реализация алгоритма
Реализация алгоритма поиска в ширину с использованием очереди на языке программирования C++ приведена ниже.
Данный алгоритм реализован в библиотеке Boost Graph Library. Для его использования необходимо выполнить следующий код:
| boost:: breadth_first_search(g2, vertex(0, g2), visitor(vis)); |
Сравнение реализаций
Для сравнения собственной реализации алгоритма и реализации в библиотеке Boost Graph Library использоваласть функция clock_gettime, которая позволяет получить текущее время. Сравнение времени выполнения этих реализаций представлено на Рис. 1.
По этому графику видно, что время выполнения реализации через BGL намного больше, чем время выполнения реализации, представленной на Рис. 1 (примерно в 20 раз).
Рис. 2 Сравнение времени выполнения алгоритма
Обе реализации алгоритма выполнялись на одном и том же графе и выводили те же данные.
Вывод
Осмелюсь предположить, что низкая скорость выполнения реализации библиотеки BGL связана с её универсальностью. Из этого исследования можно заключить, что при необходимости использования небольшого числа алгоритмов целесообразнее использовать собственную, пусть и не универсальную, реализацию.
|