Задания к расчетно-графической работе
по дисциплине»Структуры и алгоритмы обработки данных»
для студентов специальности 2201, 3 курс, 6 семестр.
Задача 1
Разработать АТД «Случайный неориентированный граф». Форма представления графа G(V, E) определяется коэффициентом насыщенности K=2E/V. Граф не содержит петель и параллельных ребер.
Интерфейс АТД «Случайный неориентированный граф» включает операции:
V( ) - опрос числа вершин в графе,
E( ) - опрос числа ребер в графе,
Directed( ) опрос типа графа (ориентированный / неориентированный)
Insert(v1,v2) вставка ребра, соединяющего вершины v1, v2,
Delete (v1,v2) удаление ребра, соединяющего вершины v1, v2,
Edge(v1,v2) опрос наличия ребра, соединяющего вершины v1, v2,
Iterator(v) создание итератора смежных вершин для вершины v,
Iterator. beg( ) опрос первой смежной вершины для вершины v,
Iterator. end( ) опрос конца списка смежных вершин для вершины v,
Iterator. next( ) опрос следующей смежной вершины для вершины v,
Show( ) вывод изображения графа на экран,
DFS(v) обход вершин при поиске в глубину от заданной вершины v,
BFS(v) обход вершин при поиске в ширину от заданной вершины v.
На основе АТД «Случайный неориентированный граф» реализовать и провести эмпирические исследования времени и вычислительной сложности алгоритма:
1) определение связности графа методом обхода в глубину,
2) поиск циклов методом обхода в глубину,
3) определение простого пути между двумя заданными вершинами методом поиска в глубину,
4) определение простой связности графа методом поиска в глубину,
5) определение двухпроходного эйлерова цикла методом поиска в глубину,
6) построения остовного леса методом поиска в глубину,
7) подсчета количества вершин, находящихся в одной связной компоненте с заданной вершиной методом поиска в глубину,
8) формирования двудольного графа с раскраской в два цвета методом поиска в глубину,
9) сортировка ребер в порядке двухпроходного эйлерова цикла методом поиска в глубину,
10) удаление вершин, не нарушающих связности графа, методом поиска в глубину,
11) определение кратчайших по количеству ребер путей из заданной вершины методом поиска в ширину, с использованием очереди ребер без дублирующих ребер,
12) определение кратчайших по количеству ребер путей для всех вершин методом поиска в ширину, ?????
13) определение диаметра графа методом поиска в ширину (предусмотреть случай несвязного графа),
14) определение высоты дерева обхода в ширину и процентного содержания ребер, просматриваемых при построении дерева,
15) рандомизированный обобщенный поиск на графе.
Задача 2
Разработать АТД «Случайный ориентированный граф». Форма представления графа G(V, E) определяется коэффициентом насыщенности K=2E/V. Граф не содержит петель и параллельных ребер.
Интерфейс АТД «Случайный неориентированный граф» включает операции:
V( ) - опрос числа вершин в графе,
E( ) - опрос числа ребер в графе,
Directed( ) опрос типа графа (ориентированный / неориентированный)
Insert(v1,v2) вставка ребра, соединяющего вершины v1, v2,
Delete (v1,v2) удаление ребра, соединяющего вершины v1, v2,
Edge(v1,v2) опрос наличия ребра, соединяющего вершины v1, v2,
Iterator(v) создание итератора смежных вершин для вершины v,
Iterator. beg( ) опрос первой смежной вершины для вершины v,
Iterator. end( ) опрос конца списка смежных вершин для вершины v,
Iterator. next( ) опрос следующей смежной вершины для вершины v,
Show( ) вывод изображения графа на экран,
DFS(v) обход вершин при поиске в глубину от заданной вершины v,
BFS(v) обход вершин при поиске в ширину от заданной вершины v.
На основе АТД «Случайный ориентированный граф» реализовать и провести эмпирические исследования времени и вычислительной сложности алгоритма:
1) вычисления транзитивного замыкания орграфа методом Уоршалла,
2) вычисления транзитивного замыкания орграфа на основе поиска в глубину,
3) определение кратчайших по числу ребер путей для всех пар вершин методом Флойда – Уоршалла,
4) построения ациклического орграфа DAG на основе поиска в глубину из случайной вершины и отбрасывания обратных ребер,
5) преобразования орграфа в ациклический орграф DAG на основе поиска в глубину и изменения ориентации любого встретившегося обратного ребра
6) подсчета числа направленных циклов методом поиска в глубину,
7) проверки того, что заданный орграф является ациклическим,
8) проверки сильной связности двух заданных вершин в орграфе,
9) определения списка достижимых вершин для заданной вершины орграфа,
10) обратной топологической сортировки ациклического орграфа DAG,
11) топологической сортировки ациклического орграфа DAG,
12) топологической сортировки ациклического орграфа DAG на основе очереди истоков,
13) вычисления числа различных простых путей из любого истока в каждую вершину ациклического орграфа DAG.
14) Построение остовного дерева от заданной вершины орграфа методом поиска в глубину,
15) Построение остовного дерева от заданной вершины орграфа методом поиска в ширину.
Задача 3
Разработать АТД «взвешенный неориентированный граф» или АТД «Взвешенный ориентированный граф» в зависимости от варианта задания. Граф не содержит петель и параллельных ребер.
На основе разработанного АТД реализовать и провести эмпирические исследования времени и вычислительной сложности алгоритма:
1) построения минимального остовного дерева взвешенного неориентированного графа методом Прима,
2) построения минимального остовного дерева взвешенного неориентированного графа методом Крускала,
3) построения минимального остовного дерева взвешенного неориентированного графа методом Прима с предварительной сортировкой ребер,
4) разбиения вершин взвешенного неориентированного графа на K кластеров таких, что ни одно ребро с длиной, большей d, не соединяет вершины из различных кластеров. Для разбиения использовать алгоритм Крускала.
5) поиска кратчайших путей из заданной вершины взвешенного орграфа во все остальные вершины методом Дейкстры,
6) поиска наиболее удаленной вершины от заданной вершины взвешенного орграфа на основе алгоритма Дейкстры,
7) определения среднего значения длины кратчайших путей из заданной вершины взвешенного орграфа в каждую другую вершину на основе алгоритма Дейкстры,
8) формирования списка ребер кратчайшего пути из вершины v в вершину u во взвешенном орграфе на основе алгоритма Дейкстры,
9) вывода всех кратчайших путей из заданной вершины взвешенного орграфа на основе алгоритма Дейкстры,
10) определения списка вершин, которые лежат в пределах заданного расстояния d от заданной вершины взвешенного орграфа на основе алгоритма Дейкстры,
11) нахождения ребер, устранение которых вызывает максимальное возрастание кратчайшего пути из вершины v в вершину u во взвешенном орграфе на основе алгоритма Дейкстры,
12) вычисление диаметра взвешенного орграфа и вывода самого длинного пути на основе алгоритма Флойда,
13) вычисление центра взвешенного орграфа и вывода самого длинного пути на основе алгоритма Флойда,
14) определения кратчайших путей из заданной вершины взвешенного орграфа с отрицательными весами ребер на основе алгоритма Беллмана – Форда,
15) определения кратчайших путей из заданной вершины взвешенного орграфа с отрицательными весами ребер на основе алгоритма Джонсона.
Методические указания.
Граф может быть представлен в виде списков смежности или матрицы смежности. Форма представления графа G(V,E) определяется коэффициентом насыщенности K=2E/V.
Обеспечить визуальный просмотр работы операции для небольших графов (V £ 10, E £ 20)
Провести тестирование случайных графов со следующими параметрами:
V = 500; E = 50, 100, 1000, 5000, 10000, 50000,
V = 10000; E = 50, 100, 1000, 5000, 10000, 50000.
В результате тестирования получить эмпирические оценки эффективности операции заданной вариантом. Оценки получить относительно размера графа, выраженные в числе просмотренных вершин, в числе просмотренных. ребер, суммарном в числе просмотренных вершин и ребер.
Список рекомендуемой литературы
Альфред Ахо, Хопкрофт, Д. Ульман Структуры данных и алгоритмы. М., Изд. "Вильямс", 2000 г. Н. Вирт Алгоритмы + структуры данных = программы. М., Изд. "Мир", 1985 г. Н. Вирт Алгоритмы и структуры данных. М., Изд. "Досса", 1997 г. У. Дал, Э. Дейкстра, К. Хоор Структурное программирование. М. "Мир", 1975 г. Д. Кнут. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М., "Мир", 1976 г., (переиздание - М., Изд. "Вильямс", 2000 г.) Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. М., "Мир", 1978 г., (переиздание - М., Изд. Изд. Вильямс", 2000 г.) Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы. Анализ и построение. М., Изд. "БИНОМ", 2000 г. Роберт Сэджвик. Фундаментальные алгоритмы на С++. Части 1-4. М., Изд. DiaSoft, 2001 г. Роберт Сэджвик. Фундаментальные алгоритмы на С++. Части 5. М., Изд. DiaSoft, 2002 г. Уильям Топп, Уильям Форд. Структуры данных в С++. М., Изд. "Бином", 2000 г. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений.: - Киев, издательство «ДиаСофт», 2001г.