«Структуры и алгоритмы компьютерной обработки данных: система двусторонних дорог» - Курсовая работа

Содержание

Введение 4

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

Решение задачи 6

Исходный код программы 11

Литература 16

Введение

Графы являются обобщенными иерархическими структурами. Граф со-стоит из множества элементов данных, называемых вершинами, и множества ребер, соединяющих эти вершины попарно. Граф мы будем обозначать G = , где V - множество вершин, Е - множество ребер.

Существует много алгоритмов на графах, в основе которых лежит систе-матический перебор вершин графа, при этом каждая вершина просматривается в точности один раз. Поэтому важной задачей является нахождение хороших методов поиска в графе. Поисковые методы для бинарных деревьев имеют свои аналоги для графов. В нисходящем обходе бинарного дерева применяется такая стратегия, при которой сначала выполняется обработка узла-, а затем уже про-движение вниз по поддереву. Обобщением прямого метода прохождения для графов является поиск "сначала в глубину" {depth - first). Начальная вершина передается в качестве параметра и становится первой обрабатываемой верши-ной. По мере продвижения вниз до тупика смежные вершины запоминаются в стеке с тем, чтобы можно было к ним вернуться и продолжить поиск по друго-му пути в случае, если еще остались необработанные вершины. Обработанные вершины образуют множество всех вершин, достижимых из начальной вершины.

Система дорог - это размеченный мультиграф (без петель), который от-личается от графа тем, что в нем одна и та же пара (различных) вершин может быть связана более чем одним ребром. При этом вершины соответствуют горо-дам, а ребра - дорогам. Односторонним дорогам соответствуют дуги, а двусто-ронним дорогам - ребра. Каждая дорога имеет некоторую длину - положитель-ное вещественное число.

Выдержка из текста работы

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

Задана система двусторонних дорог. Найти два города и соединяющий их путь, который проходит через каждую из дорог ровно один раз.

Разработать алгоритм решения этой задачи и написать программу.

Решение задачи

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

Основные теоретические положеня

Эйлеровым путем в графе называется произвольный путь, проходящий через каждое ребро графа в точности один раз, т.е. путь V1, V2, Vm+1, такой, что каждое ребро е е Е появляется в последовательности V1, V2, Vm+1 в точности один раз как е = {Vi, Vi+1} для некоторого i. Если V1 = Vm+i, то такой путь назы-вается эйлеровым циклом.

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

Эйлер представил необходимое и достаточное условие существования эйлерова пути.

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

Если в связном графе нет вершин нечетной степени, то каждый эйлеров путь является циклом.

Заключение

void _fastcall TForm1::Button1Click(TObject *Sender)

{

Image1->Picture=NULL;

Image1->Canvas->Rectangle(0,0,Width,Height);

for(int i=0;i for(int j=0;j StringGrid1->Cells[j][i]=""; //в цикле очищаем матрицу смеж-ности

n=0;//обнуляем счетчик вершин

Edit1->Text="";

Edit2->Text="";

Edit3->Text="";

}

//---------------------------------------------------------------------------

void _fastcall TForm1::FormActivate(TObject *Sender)

{

Image1->Picture=NULL;

Image1->Canvas->Rectangle(0,0,Width,Height);

}

//---------------------------------------------------------------------------

void _fastcall TForm1::Button2Click(TObject *Sender)

{ int l=0;

for (int i = 1; i<11; i++)

{

int k=0;

for (int j = 1; j<11; j++)

{if ((StringGrid1->Cells[i][j])==1)

{

k++;

}

}

if (k%2!=0)

{

l++;

}

}

AnsiString R;

int vis[11][11];

for (int i = 1; i<11; i++)

{for (int j = 1; j<11; j++)

{ vis[i][j]=0;}

}

stack S;

stack L;

if (l<3) {

int V=1;

for (int i = 1; i<11; i++)

{

int k=0;

for (int j = 1; j<11; j++)

{if ((StringGrid1->Cells[i][j])==1)

{

k++;

}

}

if (k%2!=0)

{

V=i;

break;

}

}

S.push(V);

while(!S.empty())

{

V=S.top();

int i;

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

if (((StringGrid1->Cells[i][V])==1)&&(vis[V][i]==0))

{

vis[V][i]=1;

vis[i][V]=1;

V=i;

S.push(V);

break;

}

if (i==n+1)

{

L.push(S.top());

S.pop();

}

}

Edit2->Text=L.top();

while(!L.empty())

{

R=R+L.top()+" ";

L.pop();

}

Edit1->Text=R;

Edit3->Text=R[R.Length()-1];

}

if (l>2)

{

MessageBox(0, "Граф не имеет Эйлеровый путь","Ошибка", MB_OK);

}

}

Список литературы

1. МЕТОДИЧКА. Создание графического интерфейса для работы с гра-фами (В среде С++ Builder 6)

2. Тетрадь лекций по предмету «Структуры и алгоритмы компьютерной обработки данных».