Курсовая работа
«Структуры и алгоритмы компьютерной обработки данных: система двусторонних дорог»
- 16 страниц
Введение 4
Постановка задачи 5
Решение задачи 6
Исходный код программы 11
Литература 16
Графы являются обобщенными иерархическими структурами. Граф со-стоит из множества элементов данных, называемых вершинами, и множества ребер, соединяющих эти вершины попарно. Граф мы будем обозначать G = Существует много алгоритмов на графах, в основе которых лежит систе-матический перебор вершин графа, при этом каждая вершина просматривается в точности один раз. Поэтому важной задачей является нахождение хороших методов поиска в графе. Поисковые методы для бинарных деревьев имеют свои аналоги для графов. В нисходящем обходе бинарного дерева применяется такая стратегия, при которой сначала выполняется обработка узла-, а затем уже про-движение вниз по поддереву. Обобщением прямого метода прохождения для графов является поиск "сначала в глубину" {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 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 stack 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. Тетрадь лекций по предмету «Структуры и алгоритмы компьютерной обработки данных».
Тема: | «Структуры и алгоритмы компьютерной обработки данных: система двусторонних дорог» | |
Раздел: | Информатика | |
Тип: | Курсовая работа | |
Страниц: | 16 | |
Цена: | 1000 руб. |
Закажите авторскую работу по вашему заданию.
- Цены ниже рыночных
- Удобный личный кабинет
- Необходимый уровень антиплагиата
- Прямое общение с исполнителем вашей работы
- Бесплатные доработки и консультации
- Минимальные сроки выполнения
Мы уже помогли 24535 студентам
Средний балл наших работ
- 4.89 из 5
написания вашей работы
У нас можно заказать
(Цены могут варьироваться от сложности и объема задания)
682 автора
помогают студентам
42 задания
за последние сутки
10 минут
время отклика
Взаимосвязь психологической устойчивости и адаптации учащихся профильных классов
Дипломная работа:
РАЗРАБОТКА СТРУКТУРЫ И ДИЗАЙН ИНФОРМАЦИОННЫХ РЕСУРСОВ ЦЕНТРА РАЗВИТИЯ РЕБЕНКА «KотоффKids»
Дипломная работа:
Управленческий учет, анализ и аудит коммерческо-сбытовой деятельности на примере ООО Цивилизация
Курсовая работа:
База данных компьютерного магазина
Дипломная работа:
Особенности организации документационного обеспечения деятельности коммерческой структуры и его совершенствование