Поиск эйлерова пути в графе
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Министерство образования и науки Республики Татарстан
Казанский национальный исследовательский технический университет им. А. Н. Туполева
Кафедра автоматизированных систем обработки информации и управления
КУРСОВАЯ РАБОТА
Программирование и структура данных
Выполнила
студентка группы 4209
Басырова А.Р
Проверила
доцент Э.Г. Тахавова
Казань 2011
1.Задание
Найти эйлеров путь в графе.
2.Описание применения
2.1 Постановка задачи
Разработанная программа находит Эйлеров путь в графе с количеством вершин n от 2 до 20.
В программе используются следующие определения:
Граф - пара (V;E), где V - конечное непустое множество вершин, а E - множество неупорядоченных пар вершин из V, называемых ребрами.
Путь, соединяющий вершины u и v, - это последовательность вершин , такая, что , и для любого вершины и соединены ребром.
Эйлеров путь - произвольный путь, проходящий через каждое ребро графа в точности один раз.
Теорема. Эйлеров путь существует в графе тогда и только тогда, когда граф связный и содержит не более чем две вершины нечетной степени.
Решаемая задача иллюстрируется на рисунках 2.1, 2.2 и 2.3. На рисунке 2.1 изображен граф, содержащий два эйлеровых пути: 0,1,2,3,4,2 и 0,1,2,4,3,2. Пути 2,4,3,2,1,0 и 2,3,4,2,1,0 совпадают с названными ранее. В графе, изображенном на рисунке 2.2, эйлерова пути не существует, так как в нем более двух вершин с нечетной степенью. В графе на рисунке 2.3 эйлерова пути тоже нет, так как граф несвязный.
iитается, что нужно найти любой один эйлеров путь в графе, если он существует. Если он не существует, то нужно вывести соответствующее сообщение. Граф неориентированный.
2.2 Входные данные
Входные данные представляют собой граф. Он вводится из файла, имя которого нужно указать в тексте программы. В первой строке входного файла указано количество вершин n, в следующих n строках располагается матрица смежности, элементы которой разделены пробелами. Граф, изображенный на рисунке 2.1 в файле представляется так:
01000
0100
1011
0101
0110
2.3 Выходные данные
Результатом программы является текст, содержащий последовательность вершин, составляющих эйлеров путь, если путь существует или последовательность сообщений об ошибке. Результат выводится на экран.
Примеры вывода:
Для графа на рисунке 2.1
Эйлеров путь: 0,1,2,3,4,2
Для графа на рисунке 2.2
Количество вершин нечетной степени более двух
Для графа на рисунке 2.3
Граф несвязный
2.4 Сообщения
)Недопустимое количество вершин
)Нет входного файла
)Входной файл пуст
)Граф несвязный
)Количество вершин нечетной степени более двух
граф путь программа массив
.Описание программы
.1 Метод решения задачи
Поиск эйлерова пути производится следующим образом. Функции поиска передается вершина, из которой ищется путь. Если путь является эйлеровым, то работа программы завершается выводом сообщения, содержащего этот путь. Функция находит путь от начальной вершины к другой вершине и рассматривает ее как начальную, ребро удаляется. Если от нее существуют пути в другие вершины, осуществляется такой же переход. Если же путей нет, то происходит запись вершины в результат и возврат к предыдущей вершине. Эта функция может быть описана рекурсивно, но нерекурсивный вариант более быстрый и простой, поэтому он и будет использоваться.
Алгоритм 3.1 Поиск эйлерова пути с возвратом массива, содержащего результат
[ns++]=v;//в стек заносится начальная вершина
while (ns!=0)//если стек не пуст
{
V=0;//степень вершины
v=stack[ns-1];// v - значение на вершине стека
for (i = 0; i < n; i++) V+=g[v][i];//нахождение степени вершины
if (V==0) ns--,res[no++]=v;/*если нет путей из вершины, вершина заносится в результат*/
else
{
i=0;
while (g[v][i]!=1) i++;//нахождение ребра из вершины v
g[v][i]=0;//удаление ребра
g[i][v]=0;
stack[ns++]=i;//запись второго конца ребра в стек
}
}
3.2 Структура программы
Структура программы показана на рис. 3.1.
Программа состоит из семи функционально-прочных модулей: main - главная программа, VVOD - ввод графа, prov1 - проверка на связность, prov2 - проверка степеней вершин, poisk - поиск эйлерова пути, VYVOD - вывод сообщений, marker - подiет меток.
Сопряжения модулей описаны в табл. 3.1. Все данные передаются между модулями только в виде параметров, глобальных переменных в программе нет.
Таблица 3.1 Сопряжения модулей
НомерВходВыход1-Количество вершин, матрица смежности, код завершения2Количество вершин матрица смежностиКод завершения3Количество вершин, матрица смежностиКод завершения4Начальная вершина, количество вершин, матрица смежностиМассив с результатом, указатель конца массива с результатом5Код завершения-6Количество вершин, массив меток, меткаКоличество меток в массиве
.3 Описание модулей
3.3.1 main - главный модуль
ЗАГОЛОВОК: int main() ФУНКЦИЯ: ввод графа из входного файла, проверка на связность и степени вершин, вывод сообщений, поиск эйлерова пути и его вывод на экран.
ВХОДНЫЕ ДАННЫЕ: нет
ВЫХОДНЫЕ ДАННЫЕ: нет
ЗНАЧЕНИЕ: 0 - выполнение программы завершено
РАБОЧИЕ ДАННЫЕ:
i, j, k -но