Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Генераторы графов
|
|
Чтобы углубить наше понимание различных свойств графов как комбинаторных структур, мы теперь рассмотрим подробные примеры типов графов, которыми мы позднее воспользуемся для тестирования изучаемых алгоритмов. Некоторые из этих примеров заимствованы из приложений. Другие взяты из математических моделей, которые предназначены как для исследования свойств, с какими мы можем столкнуться в реальных графах, так и для расширения диапазона входных испытаний, которые можно применять для тестирования избираемых нами алгоритмов.
С целью конкретизации примеров мы представим их в виде клиентских функций программы 17.1 с тем, чтобы их можно было непосредственно применять для тестирования реализаций алгоритмов на графах, которые мы намереваемся использовать на практике. Кроме того, мы проведем исследование реализации функции io:: scan из программы 17.4, которая производит считывание последовательности пар произвольных имен из стандартного ввода и строит граф, составленный из вершины, соответствующих именам, и ребер, соответствующих парам.
Глава 17. Свойства и типы графов
|
Реализации, которые мы рассматриваем в этом разделе, основаны на интерфейсе, содержащемся в программе 17.1, благодаря чему они функционируют должным образом, по крайней мере, теоретически, при любом представлении графа. На практике, однако, некоторые сочетания реализаций и представлений, как мы вскоре убедимся сами, не могут обеспечить приемлемой производительности.
Программа 17.12. Генератор случайных графов
(случайные ребра)_________________________
| РИСУНОК 17.12. ДВА СЛУЧАЙНЫХ ГРАФА Оба показанных на рисунке графа содержат по 50 вершин. Разреженный граф в верхней части рисунка содержит 50 ребер, в то время как насыщенный граф в нижней части рисунка — 500 ребер. Разреженный граф не относится к категории связных, поскольку каждая из его вершин соединена только с небольшим числом других вершин; насыщенный граф, несомненно, является связным, ибо каждая его вершина связана в среднем, минимум, с 20 другими вершинами. Эти диаграммы показывают, с какими трудностями сопряжена разработка алгоритмов, которые способны вычерчивать произвольные графы (в рассматриваемом случае вершины размещаются в случайно выбранных местах). |
Рассматриваемая функция добавляет в граф произвольное (случайное) ребро путем генерации Е случайных пар целых чисел, интерпретации целых чисел как вершин графа и пар меток вершин как ребер графа. Решение о том, как поступать с параллельными ребрами и петлями, возлагается на функцию-элемент Graph. В общем случае этот метод не подходит для генерации крупных насыщенных графов из-за того, что при генерации ребер появляется значительное количество параллельных ребер.
static void randE (Graph & G, int E) { for (int i = 0; i < E; i++)
{
int v = int(G.V()*rand()/
(1.0+RAND_MAX)); int w = int(G.V()*rand()/
(1.0+RANDJMAX)); G.insert(Edge(v, w))/ } }
Как обычно, мы заинтересованы в " примерах случайных задач" как в плане выполнения наших задач в условиях произвольных вводов, так и с целью получить представление о том, как будут вести себя программы в реальных приложениях. Что касается графов, то достижение второй цели сопряжено с большими трудностями, чем в других предметных областях, которые мы рассматривали ранее, хотя она все еще оправдывает затрачивав-
мые усилия. Мы столкнемся с различными моделями случайных величин, начиная со следующих двух.
Случайные ребра. Реализация этой модели довольно проста, в чем легко убедиться, ознакомившись с генератором, представленным программой 17.12. Для заданного числа вершин V мы генерируем произвольные ребра путем выбора случайных чисел в преде-