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

Графы являются обобщенными иерархическими структурами. Граф со-стоит из множества элементов данных, называемых вершинами, и множества ребер, соединяющих эти вершины попарно. Граф мы будем обозначать 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];

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

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