Алгоритм построения Эйлерова цикла

Размещено на http://www.allbest.ru/

Министерство образования Российской Федерации

Пензенский государственный университет

Кафедра «Вычислительная техника»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

по дисциплине «Логика и основы алгоритмизации в инженерных задачах»

на тему «Алгоритм построения Эйлерова цикла»

Выполнил:

студент группы 16ВB3 Бурин М.Э.

Проверил: к. т. н., доцент

Пащенко Д. В.

Малютина Г.И.

Пенза 2017



Содержание

Введение

1. Постановка задачи

2. Теоретическая часть

3. Описание алгоритма решения поставленной задачи

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

5. Тесты

Заключение

Список используемых источников

Приложение



Введение

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л.Эйлеру, появилась в 1736г. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно её приложений дало сильный толчок развитию теории графов.

В настоящее время эта теория находит многочисленное применение в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сети нефтепроводов, в программировании и теории игр, теории передачи сообщений. Теория графов теперь применяется и в таких областях, как экономика, психология и биология.

Алгоритм, реализованный в полученной программе, реализует построение Эйлерова цикла. С данным циклом как раз связана задача о кенигсбергских мостах, приведшая к исторически первой попытке развития теории графов как самостоятельного предмета. Созданная Эйлером теория графов находит очень широкое применение в транспортных и коммуникационных системах.

1. Постановка задачи

Необходимо разработать программу «Построение Эйлерова цикла» на языке Си. Пользователь должен иметь возможность ввода исходной таблицы смежности графа, на основе которой программа должна будет реализовать поиск и построение Эйлерова цикла.

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

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

Разработка будет осуществляться с использованием среды программирования MS Visual Studio. Созданная программа будет ориентирована на операционную систему MS Windows.

граф эйлер си программа

2. Теоретическая часть

Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется Эйлеровым циклом, а граф называется Эйлеровым графом.

Эйлеров цикл содержит не только все ребра по одному разу, но и все вершины графа (возможно, по несколько раз).

Чтобы в графе существовал Эйлеров цикл необходимо:

1. Граф должен быть связанным: для любых двух вершин должен существовать путь, их соединяющий.

2. Для неориентированных графов число ребер в каждой вершине должно быть четным.

3. Описание алгоритма решения поставленной задачи

Изначально была проведена работа с теорией по данной теме. В результате был найден подходящий алгоритм для решения поставленной задачи. Был спроектирован интерфейс.

В качестве среды программирования был выбран программный продукт Visual Studio 2013.

В первую очередь, с помощью форм был разработан интерфейс, удовлетворяющий решению задачи.

Затем была написана функция DialogBox(), отображающая данный интерфейс.

Следующей была реализована функция void calculate(), обрабатывающая данные, введенные пользователем. Она считывает данные, введенные пользователем, и осуществляет проверку возможности существования в графе Эйлерова цикла.

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

В итоге данная функция стала частью цикла главной функции программы BOOL CALLBACK DlgProc(). Данная функция была реализована как функция, отвечающая за алгоритм процесса работы программы и выдающая конечный результат работы. Функция использует результаты работы функции void calculate() и строит как исходный граф, введенный изначально пользователем, так и конечный Эйлеров цикл (или выдаёт информацию о его не существовании). На рисунках 1, 2 показана схема работы программы.



Рисунок 1 ? Схема данных

Рисунок 2 ? Схема работы программы



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

При запуске программы выводится окно, которое изображено на рисунке 3, с двумя текстовыми полями для ввода исходных данных, двумя полями для изображения исходного и конечного графа и кнопка запуска расчета.

Рисунок 3 - Исходное состояние

В верхнее текстовое поле пользователь должен ввести количество вершин его графа, в нижнее - матрицу смежности данного графа. Затем пользователь, нажимая на кнопку «Поиск эйлерова цикла», запускает расчет. Если пользователь правильно ввел все значения, то программа выдаст результат: будет построен исходный граф и если в нём будет найден эйлеров цикл, то он будет отображен в конечном графе. Результат работы программы показан на рисунках 4 и 5.

Рисунок 4 - Результат работы Рисунок 5 - Результат работы

5. Тесты

В качестве среды разработки была выбрана программа Visual Studio 2013. Для отладки использовались такие инструменты как точка останова, выполнение кода по шагам, анализ содержимого локальных и глобальных переменных, анализ содержимого памяти.

Тестирование проводилось в рабочем порядке, в процессе разработки, после завершения написания программы. В ходе тестирования было выявлено и исправлено множество проблем, связанных с выделением памяти.

Также были добавлены проверки, связанные с вводом исходной матрицы смежности.

Если пользователь неправильно вводит исходную матрицу смежности (допускает ошибку при вводе или указывает не соответствующее количество вершин), то после нажатия на кнопку «Поиск Эйлерова цикла» выдаётся окно с ошибкой «Ошибка ввода матрицы смежности». На рисунке 6 показан пример неверно введенных данных.

Рисунок 6 - Пример неверно введенных данных

Если же граф введен правильно, но эйлеровы циклы в нём найдены не будут, то в нижнем поле формы выведется сообщение «В данном графе нет эйлеровых циклов». Это показано на рисунке 7 и 8.

Рисунок 7 - Пример графа без эйлерова цикла



Рисунок 8 - Пример графа без эйлерова цикла



Заключение

В ходе выполнения данной курсовой работы были получены навыки обработки графов на ПК, расчета основных параметров графов. Разработаны алгоритмы построения и обработки графов. Был изучен и реализован алгоритм построения эйлерового цикла.

При выполнении данной работы использовались функции WinAPI, описанные в заголовочном файле Windows.h для визуализации результатов работы.

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



Список используемых источников

1. Язык Си: Б.В. Керниган, Д.М. Ричи - Санкт-Петербруг, Невский диалект, 2003г. - 355 с.

2. Как программировать на С: Харви Дейтел, Пол Дейтел - Москва, Бином-пресс, 2006 г. - 512 с.

3. Ресурсы электронной библиотеки http://msdn.microsoft.com/

4. Лекции по теории графов / Под ред. В.А. Емеличева., О.Н. Мельникова, В.И. Сарванова, Р.И. Тышкевич. - Москва, Наука, Гл. ред. физ.-мат. лит., 1990г. - 384 с.

5. Основы теории графов: Зыков А.А. - Москва, Наука, 1987г. - 381 с.



Приложение

Листинг программы

Файл «main.cpp»

#include <stdio.h>

#include <stdlib.h>

#include <Windows.h>

#include "resource.h"

#define _USE_MATH_DEFINES

#include <math.h>

#define GRAF_X 337

#define GRAF_Y 107

#define CYCLE_X 229

#define CYCLE_Y 351

#define GRAF_R 80

#define VERTEX_R 15

char selector = 0;

int* M; // Матрица смежности входного графа

int* M1; // В этой матрице формируется Эйлеров цикл

int n; // Количество вершин

int* coords1; // Координаты вершин исходного графа

int* coords2; // Координаты вершин эйлерова цикла

int current;

bool exist;

bool cht;

void calculate(HWND hwnd)

{

LPWSTR buffer; // Сюда записываются данные из текстового поля

int bufferlen; // Длина введенных данных

WCHAR c; // Текущий символ

int cnt1; // Счетчик считанных символов

int cnt2; // Счетчик считанных символов одного значения

int cnt3; // Счетчик считанных значений

bool f; // Флаг анализа первой строки

int vnum;

int min;

int vmin;

int cnt = 1;

WCHAR tnum[10]; // Буфер значения

// Переносим данные из текстового поля в буфер

bufferlen = (int)SendMessage(GetDlgItem(hwnd, IDC_EDIT1), WM_GETTEXTLENGTH , 0, 0) + 1; // Вычисляем длину введенных данных

buffer = (LPWSTR)malloc(bufferlen*2); // Выделяем место

GetDlgItemText(hwnd, IDC_EDIT1, buffer, bufferlen); // Считываем данные

n = GetDlgItemInt(hwnd, IDC_EDIT2, NULL, FALSE);

// Переносим данные из текстового буфера в матрицу

cnt1 = 0;

cnt2 = 0;

cnt3 = 0;

f = true;

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

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

while (1)

{

c = *(buffer + cnt1);

cnt1++;

if (c != L' ' && c != L'\n' && c != L'\0' && c != '\r')

{

tnum[cnt2] = c;

cnt2++;

}

if (c == L' ' || c == L'\n')

{

tnum[cnt2] = '\0';

M[cnt3] = _wtoi(tnum);

cnt3++;

cnt2 = 0;

}

if (c == L'\0')

{

tnum[cnt2] = '\0';

M[cnt3] = _wtoi(tnum);

cnt3++;

cnt2 = 0;

break;

}

}

// Обработка ошибок

if (cnt3 != n * n)

{

MessageBox(hwnd, L"Ошибка ввода матрицы смежности", L"Error", 0);

PostQuitMessage(0);

}

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

{

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

{

if (M[i * n + j] != M[j * n + i] || (j == i && M[i * n + j] != 0))

{

MessageBox(hwnd, L"Ошибка ввода матрицы смежности", L"Error", 0);

PostQuitMessage(0);

}

}

}

// Проверка на существование ЭЦ

cht = true;

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

{

int s = 0;

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

{

s += *(M + i*n + j);

}

if (s % 2 != 0)

{

cht = false;

break;

}

}

if (cht)

{

exist = true;

// Модифицируем матрицу смежности

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

{

if (*(M + i) == 0)

{

*(M1 + i) = 200000;

} else {

*(M1 + i) = 0;

}

}

vnum = 0;

while (f)

{

min = 200000;

// Находим ребро с минимальной нумерацией

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

{

if (*(M1 + vnum*n + i) < min)

{

vmin = i;

min = *(M1 + vnum*n + i);

}

}

*(M1 + vnum*n + vmin) = cnt;

*(M1 + vmin*n + vnum) = cnt;

cnt++;

vnum = vmin;

if (vnum == 0)

{

f = false;

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

{

if (*(M1 + i) == 0)

{

f = true;

}

}

}

}

min = 200000;

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

{

if (*(M1 + i) < min)

{

min = *(M1 + i);

}

}

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

{

*(M1 + i) -= min - 1;

}

} else {

exist = false;

}

// Вычисляем координаты вершин

coords1 = (int*)malloc(n*2*sizeof(int));

coords2 = (int*)malloc(n*2*sizeof(int));

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

{

*(coords1 + i*2) = GRAF_X + GRAF_R * cos(M_PI*2*i/n);

*(coords1 + i*2 + 1) = GRAF_Y + GRAF_R * sin(M_PI*2*i/n);

*(coords2 + i*2) = CYCLE_X + GRAF_R * cos(M_PI*2*i/n);

*(coords2 + i*2 + 1) = CYCLE_Y + GRAF_R * sin(M_PI*2*i/n);

}

}

BOOL CALLBACK DlgProc(HWND hwnd, UINT uMsg, WPARAM wParam, LPARAM lParam)

{

HDC hdc;

RECT r = {0, 0, 1000, 1000};

PAINTSTRUCT ps;

char str[10];

if (uMsg == WM_COMMAND)

{

switch(LOWORD(wParam))

{

case IDCANCEL:

return EndDialog(hwnd,IDCANCEL);

case IDC_BUTTON1:

selector = 1;

calculate(hwnd);

InvalidateRect(hwnd, &r, 0);

break;

default:

return 0;

}

}

if (uMsg == WM_PAINT)

{

hdc = BeginPaint(hwnd, &ps);

GetClientRect (hwnd, &r);

FillRect (hdc, &r, (HBRUSH)(COLOR_WINDOW));

Rectangle(hdc, 234, 10, 441, 205);

Rectangle(hdc, 126, 254, 333, 449);

if (selector == 1)

{

// Вывод ребер исходного графа

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

{

for (int j = i + 1; j < n; j++)

{

if (*(M + i*n + j) != 0)

{

MoveToEx(hdc, *(coords1 + i * 2), *(coords1 + i * 2 + 1), NULL);

LineTo(hdc, *(coords1 + j * 2), *(coords1 + j * 2 + 1));

}

}

}

// Вывод вершин

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

{

itoa(i + 1, str, 10);

Ellipse(hdc, *(coords1 + i*2) - VERTEX_R,

*(coords1 + i*2 + 1) - VERTEX_R,

*(coords1 + i*2) + VERTEX_R,

*(coords1 + i*2 + 1) + VERTEX_R);

TextOutA(hdc, *(coords1 + i*2) - strlen(str)*4,

*(coords1 + i*2 + 1) - 8,

str, strlen(str));

}

if (exist)

{

// Вывод ребер конечного графа

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

{

for (int j = i + 1; j < n; j++)

{

if (*(M + i*n + j) == 1)

{

itoa(*(M1 + i*n + j), str, 10);

MoveToEx(hdc, *(coords2 + i * 2), *(coords2 + i * 2 + 1), NULL);

LineTo(hdc, *(coords2 + j * 2), *(coords2 + j * 2 + 1));

TextOutA(hdc, *(coords2 + i * 2) + (*(coords2 + j * 2) - *(coords2 + i * 2)) * 1 / 4 - strlen(str)*4,

*(coords2 + i * 2 + 1) + (*(coords2 + j * 2 + 1) - *(coords2 + i * 2 + 1)) * 1 / 4 - 8,

str, strlen(str));

}

}

}

// Вывод вершин

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

{

itoa(i + 1, str, 10);

Ellipse(hdc, *(coords2 + i*2) - VERTEX_R,

*(coords2 + i*2 + 1) - VERTEX_R,

*(coords2 + i*2) + VERTEX_R,

*(coords2 + i*2 + 1) + VERTEX_R);

TextOutA(hdc, *(coords2 + i*2) - strlen(str)*4,

*(coords2 + i*2 + 1) - 8,

str, strlen(str));

}

} else {

TextOutA(hdc, 160, 330, "В данном графе нет", 18);

TextOutA(hdc, 166, 350, "эйлеровых циклов", 16);

}

}

}

return false;

}

int WINAPI WinMain(HINSTANCE hInst, HINSTANCE hPrevInst, LPSTR lpCmdLine, int nShowCmd)

{

DialogBox(hInst, MAKEINTRESOURCE(IDD_DIALOG1), NULL, DlgProc);

}

Файл «resource.h»

#include <Windows.h>

#define IDD_DIALOG1 100

#define IDC_BUTTON1 101

#define IDC_BUTTON2 102

#define IDC_BUTTON3 103

#define IDC_BUTTON4 104

#define IDC_EDIT1 105

#define IDC_EDIT2 106

#define IDC_STATIC 107

Файл «Kurs.rc»

#include "resource.h"

IDD_DIALOG1 DIALOGEX 400, 200, 301, 285

STYLE DS_SETFONT | DS_FIXEDSYS | WS_MINIMIZEBOX | WS_POPUP | WS_CAPTION | WS_SYSMENU

EXSTYLE WS_EX_APPWINDOW

CAPTION "Поиск эйлерова цикла"

FONT 8, "MS Shell Dlg", 400, 0, 0x1

BEGIN

EDITTEXT IDC_EDIT1,7,22,137,104,ES_MULTILINE | ES_AUTOHSCROLL | ES_WANTRETURN | WS_VSCROLL | WS_HSCROLL

PUSHBUTTON "Поиск эйлерова цикла",IDC_BUTTON1,7,132,288,18

EDITTEXT IDC_EDIT2,80,7,64,12,ES_AUTOHSCROLL

LTEXT "Количество вершин:",IDC_STATIC,8,8,71,8

END

Размещено на Allbest.ru

...