Поиск эйлерова пути в графе

Министерство образования и науки Республики Татарстан Казанский национальный исследовательский технический университет им. А. Н. Туполева Кафедра автоматизированных систем обработки информации и управления КУРСОВАЯ РАБОТА Программирование и структура данных Выполнила студентка группы 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 эйлерова пути тоже нет, так как граф несвязный.

Считается, что нужно найти любой один эйлеров путь в графе, если он существует. Если он не существует, то нужно вывести соответствующее сообщение. Граф неориентированный.

2.2. Входные данные Входные данные представляют собой граф. Он вводится из файла, имя которого нужно указать в тексте программы. В первой строке входного файла указано количество вершин n, в следующих n строках располагается матрица смежности, элементы которой разделены пробелами. Граф, изображенный на рисунке 2.1 в файле представляется так:

5

0 1 0 0 0

1 0 1 0 0

0 1 0 1 1

0 0 1 0 1

0 0 1 1 0

2.3. Выходные данные Результатом программы является текст, содержащий последовательность вершин, составляющих эйлеров путь, если путь существует или последовательность сообщений об ошибке. Результат выводится на экран.

Примеры вывода:

Для графа на рисунке 2.1

Эйлеров путь: 0,1,2,3,4,2

Для графа на рисунке 2.2

Количество вершин нечетной степени более двух Для графа на рисунке 2.3

Граф несвязный

2.4. Сообщения

5) Недопустимое количество вершин

3) Нет входного файла

4) Входной файл пуст

6) Граф несвязный

7) Количество вершин нечетной степени более двух граф эйлеров путь программа

3. Описание программы

3.1. Метод решения задачи Поиск эйлерова пути производится следующим образом. Функции поиска передается вершина, из которой ищется путь. Если путь является эйлеровым, то работа программы завершается выводом сообщения, содержащего этот путь. Функция находит путь от начальной вершины к другой вершине и рассматривает ее как начальную, ребро удаляется. Если от нее существуют пути в другие вершины, осуществляется такой же переход. Если же путей нет, то происходит запись вершины в результат и возврат к предыдущей вершине. Эта функция может быть описана рекурсивно, но нерекурсивный вариант более быстрый и простой, поэтому он и будет использоваться.

Алгоритм 3.1 Поиск эйлерова пути с возвратом массива, содержащего результат

stack[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 — подсчет меток.

Сопряжения модулей описаны в табл. 3.1. Все данные передаются между модулями только в виде параметров, глобальных переменных в программе нет.

Таблица 3.1 Сопряжения модулей

3.3. Описание модулей

3.3.1. main — главный модуль ЗАГОЛОВОК: int main () ФУНКЦИЯ: ввод графа из входного файла, проверка на связность и степени вершин, вывод сообщений, поиск эйлерова пути и его вывод на экран.

ВХОДНЫЕ ДАННЫЕ: нет ВЫХОДНЫЕ ДАННЫЕ: нет ЗНАЧЕНИЕ: 0 — выполнение программы завершено РАБОЧИЕ ДАННЫЕ:

i, j, k — номера вершин

n — количество вершин

g, t — матрицы смежности графа, t — копия g

res — массив, содержащий результат АЛГОРИТМ: см. алгоритм 3.2., рис. 3.2.

Алгоритм 3.2. Алгоритм модуля main

if (VVOD (&n, g)≠0) {Vyvod (VVOD (&n, g));return 0;} //ошибка ввода

if (prov1(n, g)==6) {Vyvod (prov1(n, g));return 0;} //проверка на связность

if (prov2(n, g)==7) {Vyvod (prov2(n, g));return 0;} //проверка на степень вершин

j=0;

while (j

{ no=0; //указатель конца массива результата

for (i = 0; i < n; i++) for (k = 0; k< n; k++) t[i][k]=g[i][k]; //копия матрицы смежности

Poisk (j, n, t,&no, res); //поиск пути в графе от вершины j

k=0;

for (i = 0; i < no-1; i++)

{

if (g[res[i]][res[i+1]]==1) k++; /*проверка массива результата на наличие ребер в матрице смежности*/

}

if (k==no-1) break; //эйлеров путь найден, выход из цикла перебора вершин

j++;

}

for (i = no-1; i >=0; i—)

{

printf («%dn», res[i]); //печать результата

}

getch ();

return 0;

3.3.2. VVOD — ввод графа ЗАГОЛОВОК: int VVOD (int *n, int g[][NMAX])

ФУНКЦИЯ: ввод графа из файла f в виде матрицы смежности, перед которой указывается количество вершин n. NMAX — максимальное количество вершин.

ВХОДНЫЕ ДАННЫЕ: количество вершин n, матрица смежности g.

ВЫХОДНЫЕ ДАННЫЕ:

n — количество вершин графа;

g — матрица смежности графа (первые n строк и n столбцов матрицы NMAX*NMAX).

ЗНАЧЕНИЕ:

5 — недопустимое количество вершин;

4 — файл пуст;

3 — нет входного файла;

0 — ввод завершен без ошибок РАБОЧИЕ ДАННЫЕ:

i, j — номера вершин;

*f — указатель на входной файл АЛГОРИТМ: см. алгоритм 3.3., рис. 3.3.

Алгоритм 3.3 Алгоритм модуля VVOD

//ввод количества вершин и графа из файла

if ((f=fopen («f.txt» ," r"))≠NULL) //файл существует, открытие для чтения

(*n>20)) return 5; //недопустимое количество вершин

if (feof (f)) return 4; //файл пуст

for (i=0;i<(*n);i++)

for (j=0;j<(*n);j++)

fscanf (f," %d" ,&g[i][j]); //ввод матрицы смежности

else return 3; //нет входного файла

return 0; //успешное завершение

3.3.3. prov1 — проверка на связность ЗАГОЛОВОК: int prov1(int n, int g[][NMAX])

ФУНКЦИЯ: проверка графа на связность.

ВХОДНЫЕ ДАННЫЕ: количество вершин n, матрица смежности g.

ВЫХОДНЫЕ ДАННЫЕ: код завершения — граф связный/несвязный ЗНАЧЕНИЕ:

0 — граф связный

6 — граф несвязный РАБОЧИЕ ДАННЫЕ:

v — начальная вершина

massiv — массив меток

i, j — номера вершин АЛГОРИТМ: см. алгоритм 3.4., рис. 3.4.

Алгоритм 3.4 Алгоритм модуля prov1

int *massiv=(int*)malloc (sizeof (int)*n); /*создание массива меток, где номер ячейки — вершина, содержимое — метка*/

for (int i=0; i < n; i++) massiv[i]=1; //все вершины помечены 1

massiv[v]=2; //метка начальной вершины

while (marker (n, massiv, 2)≠0) //есть вершины, помеченные 2

{

for (int i=0; i < n; i++) if (massiv[i]==2){ v=i; break;} //переход к вершине, связанной с v

massiv[v]=3;

for (int j=0; j < n; j++) if ((g[v][j]==1)||(massiv[j]==1)) massiv[j]=2; /*метка связанных вершин*/

}

for (int i=0; i < n; i++) if (massiv[i]==1) return 6; //граф несвязный

return 0; //граф связный

3.3.4. prov2 — проверка степеней вершин ЗАГОЛОВОК: int prov2(int n, int g[][NMAX])

ФУНКЦИЯ: подсчет степеней вершин, если вершин нечетной степени более двух, то не существует эйлерова пути в графе.

ВХОДНЫЕ ДАННЫЕ: количество вершин n, матрица смежности g.

ВЫХОДНЫЕ ДАННЫЕ: код завершения — эйлеров путь есть/нет.

ЗНАЧЕНИЕ:

0 — вершин нечетной степени не больше двух

7 — вершин нечетной степени больше двух РАБОЧИЕ ДАННЫЕ:

i, j — номера вершин

k — степень вершины

t — количество вершин нечетной степени АЛГОРИТМ: см. алгоритм 3.5., рис. 3.5.

Алгоритм 3.5 Алгоритм модуля prov2

t=0;

k=0;

for (i=0;i

{for (j=0;j

if (k%2≠0) t++; //степень вершины нечетная

if (t>2) return 7; //нечетных вершин более двух

k=0;

}

return 0;

3.3.5. poisk — поиск эйлерова пути ЗАГОЛОВОК: void Poisk (int v, int n, int g[][NMAX], int *no, int res[NMAX])

ФУНКЦИЯ: нахождение эйлерова пути в графе.

ВХОДНЫЕ ДАННЫЕ: начальная вершина v, количество вершин n, матрица смежности g.

ВЫХОДНЫЕ ДАННЫЕ: массив с результатом, указатель конца массива.

ЗНАЧЕНИЕ: нет.

РАБОЧИЕ ДАННЫЕ:

i, j — номера вершин;

stack — стек;

ns — указатель на следующий после последнего элемента стека;

V — степень вершины;

АЛГОРИТМ: см. алгоритм 3.6., рис. 3.6.

Алгоритм 3.6 Алгоритм модуля poisk

ns=0;

V=0;

stack[ns++]=v; //занос начальной вершины в стек

while (ns≠0) //стек не пуст

{

V=0;

v=stack[ns]; //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++; //нахождение ребра

g[v][i]=0; //удаление ребра

g[i][v]=0;

stack[ns++]=i; //занос второго конца ребра в стек

}

}

3.3.6. VYVOD — вывод сообщений ЗАГОЛОВОК: void Vyvod (int pr)

ФУНКЦИЯ: вывод сообщений, полученных при вызове других модулей.

ВХОДНЫЕ ДАННЫЕ: код завершения, полученный при вызове одного из модулей.

ВЫХОДНЫЕ ДАННЫЕ: нет.

ЗНАЧЕНИЕ: нет.

РАБОЧИЕ ДАННЫЕ: нет.

АЛГОРИТМ: см. алгоритм 3.7., рис. 3.7.

Алгоритм 3.7 Алгоритм модуля VYVOD

switch (pr)

{

case 5: {printf («недопустимое количество вершин»);getch ();break;}

case 3: {printf («нет входного файла»);getch ();break;}

case 4: {printf («файл пуст»);getch ();break;}

case 6: {printf («нет эйлерова пути: граф несвязный»);getch ();break;}

case 7: {printf («нет эйлерова пути: вершин нечетной степени более 2»);getch ();break;}

default:

;

}

3.3.7. marker — подсчет меток ЗАГОЛОВОК: int marker (int n, int massiv[], int metka)

ФУНКЦИЯ: подсчет вершин, помеченных определенным значением.

ВХОДНЫЕ ДАННЫЕ: количество вершин n, массив меток massiv[], метка metka.

ВЫХОДНЫЕ ДАННЫЕ: количество помеченных вершин.

ЗНАЧЕНИЕ: нет.

РАБОЧИЕ ДАННЫЕ:

i — номер вершины;

result — количество помеченных вершин АЛГОРИТМ: см. алгоритм 3.8., рис. 3.8.

Алгоритм 3.8 Алгоритм модуля marker

result=0;

for (int i = 0; i < n; i++) if (massiv[i]==metka) result++; //подсчет помеченных вершин

return result; //возврат количества помеченных вершин

4. Подготовка к отладке программы

4.1. План отладки Работа практически всех модулей зависит от работы модуля VVOD, следовательно, его нужно отлаживать в первую очередь. Модуль VYVOD связан с модулем main: VYVOD выводит сообщения, возникающие при работе main, его нужно отлаживать параллельно. Правильность работы модуля poisk также тесно связан с главной программы, их работу необходимо синхронизировать. Работа модуля prov1 зависит от работы модуля marker, их нужно отлаживать вместе. А работа же модулей prov1 и prov2 может быть отлажена независимо от других модулей (за исключением нюанса, возникающего между prov1 и marker. Следовательно, получаем следующие этапы отладки:

1) Тестирование модуля VVOD

2) Тестирование модулей prov1 и marker

3) Тестирование prov2

4) Тестирование VYVOD и main

5) Тестирование модулей poisk и main

6) Тестирование всей программы

4.2. Проектрирование тестов

4.2.1. Тесты черного ящика Для проектирования тестов программы методами черного ящика с помощью эквивалентного разбиения входных и выходных данных на области эквивалентности составлен список ситуаций, каждая из которых должна создаваться хотя бы одним тестом. Тестовые ситуации приведены в табл. 4.1, в скобках указаны их номера.

Таблица 4.1 Области входных/выходных данных тестов программы

Для создания перечисленных тестовых ситуаций разработаны тесты, представленные в табл. 4.2. Входные и выходные данные тестов по возможности выбирались ближе к границам классов эквивалентности.

Таблица 4.2 Тесты черного ящика для отладки программы

4.2.2. Тесты белого ящика Разработанные тесты проверены методами белого ящика по критериям охвата основных путей выполнения алгоритмов модулей. В программе имеются составные условия. Поэтому использован критерий комбинаторного покрытия условий.

Таблица 4.3 Комбинаторное покрытие условий тестами черного ящика

* значение V всегда становится равным нулю, можно считать, что это условие не бывает ложным Из табл. 4.3 видно, что тесты черного ящика не обеспечивают истинное значение условия k%2≠0 в модуле prov2, т. е. остаток от деления на два степени вершины. Для покрытия истинного значения этого условия разработан тест, представленный в табл. 4.4.

Таблица 4.4 Тесты белого ящика

4.3. Отладка программы Программа отлажена по плану на всех предусмотренных в нем тестах.

Во время отладки были обнаружены следующие ошибки:

1) В модуле prov1 в условии (g[v][j]==1)||(massiv[j]==1) нужно условие или заменит на и, программа в первом случае работает некорректно, по исправлении же условия стали выполняться.

2) В модуле поиск при присвоении v верхнего значения стека, указатель стека следовало уменьшить на единицу, так как указатель ссылается на последующий свободный после последнего элемент.

СПИСОК ЛИТЕРАТУРЫ

1. Касьянов В. Н., Сабельфельд В. К. Сборник заданий по практимуму на ЭВМ. М.:Наука, 1986.

2. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

3. Хохлов Д. Г. Основы технологии модульного программирования: Учебное пособие. Казань: Изд-во Казан. гос. техн. ун-та, 2005.

4. Белецкий Я. Энциклопедия языка Си. М.: Мир, 1992.

5. Хохлов Д. Г. структуры данных и комбинаторные алгоритмы: Учебное пособие. Казань: Изд-во Казан. гос. техн. ун-та, 2006. 102 с.

Приложение 1

Текст программы

#include

#include

#include

#define NMAX 20

int prov2(int n, int g[][NMAX])

{

int i, j, t=0,k=0;

for (i=0;i

{for (j=0;j

if (k%2≠0) t++;

if (t>2) return 7;

k=0;

}

return 0;

}

void Poisk (int v, int n, int g[][NMAX], int *no, int res[NMAX])

{

int stack[NMAX]={0}, ns=0,V=0,i, j;

stack[ns++]=v;

while (ns≠0)

{

V=0;

v=stack[ns-1];

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++;

g[v][i]=0;

g[i][v]=0;

stack[ns++]=i;

}

}

}

int VVOD (int *n, int g[][NMAX])

{

int i, j;

FILE *f;

if ((f=fopen («<�адрес входного файла>» ," r"))≠NULL)

else return 3;

return 0;

}

int marker (int n, int massiv[], int metka)

{

int result=0;

for (int i = 0; i < n; i++) if (massiv[i]==metka) result++;

return result;

}

int prov1(int n, int g[][NMAX])

{

int v=0;

int *massiv=(int*)malloc (sizeof (int)*n);

for (int i=0; i < n; i++) massiv[i]=1;

massiv[v]=2;

while (marker (n, massiv, 2)≠0)

{

for (int i=0; i < n; i++) if (massiv[i]==2){ v=i; break;}

for (int i=0; i < n; i++) printf («%dn», massiv[i]);

printf («n»);

massiv[v]=3;

for (int j=0; j < n; j++) if ((g[v][j]==1)&&(massiv[j]==1)) massiv[j]=2;

}

for (int i=0; i < n; i++) if (massiv[i]==1) return 6;

return 0;

}

void Vyvod (int pr)

{

switch (pr)

{

case 5: {printf («nedopustimoe kolichestvo vershin»);getch ();break;}

case 3: {printf («net vhodnogo faila»);getch ();break;}

case 4: {printf («file pust»);getch ();break;}

case 6: {printf («net ejlerova puty: graf nesvjazniy»);getch ();break;}

case 7: {printf («net ejlerova puty: vershin nechetnoy stepeny bolee2»);getch ();break;}

default:

;

}

}

int main ()

{

int i, j, k, n, no=0,g[NMAX][NMAX], t[NMAX][NMAX], res[NMAX];

if (VVOD (&n, g)≠0) {Vyvod (VVOD (&n, g));return 0;}

if (prov1(n, g)==6) {Vyvod (prov1(n, g));return 0;}

if (prov2(n, g)==7) {Vyvod (prov2(n, g));return 0;}

j=0;

while (j

{ no=0;

for (i = 0; i < n; i++) for (k = 0; k < n; k++) t[i][k]=g[i][k];

Poisk (j, n, t,&no, res);

k=0;

for (i = 0; i < no-1; i++)

{

if (g[res[i]][res[i+1]]==1) k++;

}

if (k==no-1) break;

printf («nno= %in», no);

j++;

}

for (i = no-1; i >=0; i—)

{

printf («%dn», res[i]);

}

getch ();

return 0;

}

//—————————————————————————————————————;