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

Курсовой проект

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

на тему "Алгоритм Прима"



Содержание

• Введение
• 1. Постановка задачи
• 2. Теоретическая часть задания
• 3. Описание алгоритма решения поставленной задачи
• 4. Пример ручного расчета задачи и вычислений
• 5. Описание программы
• 6. Тесты
• Заключение
• Список литературы
• Приложение А. Листинги программы
• Приложение B. Результат работы программы



Введение

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

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

Тема данной курсовой является алгоритм Прима - алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.

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



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

Пользователь должен осуществить ввод матрицы весов исходного графа. По данной матрице весов будет построен и выведен граф. Затем будет найден остов исходного графа и выведен в интерфейсе программы.

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

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

В качестве среды разработки была выбрана программа MS Visual Studio 2017, а языком программирования - C#. Созданная программа будет ориентирована на операционную систему MS Windows.

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

Нам дана матрица весов С(G) графа G. Необходимо найти матрицу весов полученного остова и величину минимального остова.

Для того, чтобы найти остов, а также величину его минимального значения, необходимо выполнить следующие действия:

Выберем в графе G ребро х = v,w минимального веса и построим дерево G₁ = (V₁,X₁), полагая V₁ = {v,w}, X₁ = {х}.

Если дерево G_к уже построено и k < n-1, то среди ребер, соединяющих вершины этого дерева с вершинами графа G, не входящими в G_к, выбираем ребро y минимального веса. Строим дерево G_к+1, присоединяя к G_к ребро y вместе с его не входящим в G_к концом.

По введенной пользователем матрице весов будет построен соответствующий граф G (рис. 1).

Затем исходя из той же матрицы будет найдена матрица весов графа остова T, путем перебора всех соединений вершин и выбора ребер с минимальным весом так, что каждая вершина графа остова будет связана хотя бы с одной другой вершиной, при этом граф не будет иметь циклов. А также построен граф T по найденной матрице (рис. 2).

Рисунок 2 (а, б) - Граф G и граф T

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

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

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

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

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

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

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

Помимо этого в программе реализована функция DrawBaseGraph(), которая осуществляет отрисовку исходного графа. Блок-схема данной функции изображена на рисунке 5 и рисунке 6.



Рисунок 3 - Блок-схема функции ReadMatrix()

Рисунок 4 - Блок-схема функции Calculate()

Рисунок 5 - Блок-схема функции DrawBaseGraph() Начало.

Рисунок 6 - Блок-схема функции DrawBaseGraph() Продолжение.

4. Пример ручного расчета задачи и вычислений

На рисунке 7 изображен граф, выбранный для ручного расчета.

Рисунок 7 - Граф для ручного расчета

Выберем произвольную вершину. Для примера возьмем вершину номер 1. Ей инцидентны ребра (с неиспользованными вершинами): 1-2(5), 1-3(1), 1-5(2). В скобках указан вес ребра. Ребро с наименьшим весом 1-3(1). Включим его и инцидентную ему вершину в дерево.

Вершинам 1 и 3 инцидентны ребра (с неиспользованными вершинами): 1-2(5), 1-5(2), 3-2(3), 3-4(4). Ребро с наименьшим весом 1-5(2). Включим его и инцидентную ему вершину в дерево.

Вершинам 1, 3 и 5 инцидентны ребра (с неиспользованными вершинами): 1-2(5), 3-2(3), 3-4(4), 5-4(11). Ребро с наименьшим весом 3-2(3). Включим его и инцидентную ему вершину в дерево.

Вершинам 1, 2, 3 и 5 инцидентны ребра (с неиспользованными вершинами): 3-4(4), 5-4(11). Ребро с наименьшим весом 3-4(4). Включим его и инцидентную ему вершину в дерево.

Все вершины графа включены в дерево. Работа алгоритма завершена.



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

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

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

В верхнее текстовое поле пользователь должен ввести матрицу весов исходного графа. При нажатии на кнопку "Найти остов и построить граф", программа считывает матрицу, выводит матрицу весов остова, строит исходный граф G и остов T. (рис. 9)



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

При нажатии на кнопку очистить программа удаляет содержимое все элементов вывода, для осуществления повторного ввода.

6. Тесты

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

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

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

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

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



Заключение

алгоритм граф интерфейс программирование

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

Были получены навыки разработки приложения на языке программирования C# и навыки работы с графическим интерфейсом, а также программной платформой.NET Framework.



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

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

2. CLR via C#. Программирование на платформе Microsoft .NET Framework 4.0 на языке C# - Джеффри Рихтер, Издательство: Питер, 2012г.

3. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн - Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. - М.:Издательский дом "Вильямс", 2010. - с.653 - 656.

4. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ 2е изд. "Вильямс", 2006.

5. С. Дасгупта, Х. Пападимитриу, У. Вазирани. Алгоритмы. Глава 4. Пути в графах. Москва Издательство МЦНМО 2014 перевод с Английского.

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



Приложение А. Листинги программы

Файл Form1.cs

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

using System.IO;

using System.Collections.Generic;

namespace ILCourseGparh

{

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

}

int MWidth, MHieght,i=0,j=0;

List<int> VershX = new List<int>();

List<int> VershY = new List<int>();

List<int> DrawCoordinatsX = new List<int>();

List<int> DrawCoordinatsY = new List<int>();

List<int> weight = new List<int>();

int way = 0;

int min = 100, positionI = 0, positionJ = 0, count, numelement = 0;

List<int> OriginVershX = new List<int>();

List<int> OriginVershY = new List<int>();

List<int> OriginDrawCoordinatsX = new List<int>();

private void textBox1_TextChanged(object sender, EventArgs e)

{

}

List<int> OriginDrawCoordinatsY = new List<int>();

List<int> Oweight = new List<int>();

private void button2_Click(object sender, EventArgs e)

{

Graphics drawc_ = this.CreateGraphics();

drawc_.FillRectangle(Brushes.WhiteSmoke, 0, 0, 1000, 1000);

textBox1.Text = "";

textBox2.Text = "";

pictureBox1.Image = null;

pictureBox2.Image = null;

VershX.RemoveRange (0,VershX.Count);

VershY.RemoveRange(0, VershY.Count);

DrawCoordinatsX.RemoveRange(0, DrawCoordinatsX.Count);

DrawCoordinatsY.RemoveRange(0, DrawCoordinatsY.Count);

weight.RemoveRange(0, weight.Count);

OriginVershX.RemoveRange(0, OriginVershX.Count);

OriginVershY.RemoveRange(0, OriginVershY.Count);

OriginDrawCoordinatsX.RemoveRange(0, OriginDrawCoordinatsX.Count);

OriginDrawCoordinatsY.RemoveRange(0, OriginDrawCoordinatsY.Count);

Oweight.RemoveRange(0, Oweight.Count);

MHieght = 0; MWidth = 0;

count = 0;

positionI = 0; positionJ = 0; count=0; numelement = 0;

way = 0;

}

double angle, plus, xc, yc;

private void read_mtarix(object sender, EventArgs e)

{

try

{

char[] CharV = textBox1.Text.ToCharArray();

MHieght = textBox1.Lines.Length;

for (int i = 0; i < CharV.Length; i++)

{

if (CharV[i] == ' ') continue;

else

{

if ((CharV[i] != '\r') && (CharV[i + 1] != ' ') && (CharV[i + 1] != '\r'))

{

MWidth++;

i++;

continue;

}

if ((CharV[i] != '\r'))

{

MWidth++;

}

else

{

break;

}

}

}

if (MHieght == MWidth)

{

int[,] vershini = new int[MWidth, MHieght];

int[,] OSTOV = new int[MWidth, MHieght];

int[,] M = new int[MWidth, MHieght];

for (int i = 0, x = 0, y = 0; i < CharV.Length; i++)

{

if (CharV[i] == ' ') continue;

else if ((CharV[i] != '\r') && (CharV[i] != '\n'))

{

if (i < CharV.Length - 1)

{

if (((CharV[i] != '\r') && (CharV[i] != '\n')) && ((CharV[i + 1] != '\r') && (CharV[i + 1] != '\n') && (CharV[i + 1] != ' ')))

{

string T1 = Convert.ToString(CharV[i]);

string T2 = Convert.ToString(CharV[i + 1]);

vershini[x, y] = int.Parse(T1 + T2);

y++;

i++;

}

else

{

vershini[x, y] = int.Parse(Convert.ToString(CharV[i]));

y++;

}

}

if (y >= MWidth) y = 0;

}

else

{

i++;

x++;

}

}

DrawBaseGraph(vershini);

Calculate(vershini, OSTOV,M);

}

else { MessageBox.Show("Некорректно введена матрица", "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Exclamation, MessageBoxDefaultButton.Button1); }

}

catch

{

MessageBox.Show("Некорректно введена матрица.", "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Exclamation, MessageBoxDefaultButton.Button1);

}

}

public void Calculate(int[,] vershini, int [,]OSTOV, int[,]M)

{

System.Drawing.SolidBrush elipse = new System.Drawing.SolidBrush(System.Drawing.Color.DeepSkyBlue);

System.Drawing.Graphics SolidElipse = pictureBox1.CreateGraphics();

System.Drawing.Font Font = new System.Drawing.Font("Arial", 12);

System.Drawing.Font Font2 = new System.Drawing.Font("Arial", 16);

System.Drawing.Font Font3 = new System.Drawing.Font("Arial", 12);

Graphics GrapWriterr = pictureBox1.CreateGraphics();

Graphics TextWriterr = this.CreateGraphics();

Pen GP = new Pen(Color.Red, 2);

count = MHieght;

j = 0; i = 0;

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

{

M[i, 0] = vershini[i, 0];

M[0, i] = vershini[0, i];

}

i = 0;

j = 0;

for (int d = 0; d < MWidth-1; d++)

{

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

{

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

{

if ((M[i, j] < min) && (M[i, j] >= 1))

{

min = M[i, j];

positionI = i;

positionJ = j;

}

}

} ;

OSTOV[positionJ, positionI] = min;

OSTOV[positionI, positionJ] = min;

vershini[positionI, positionJ] = 0;

vershini[positionJ, positionI] = 0;

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

{

M[i, positionJ] = vershini[i, positionJ];

M[positionJ, i] = vershini[positionJ, i];

M[i, positionI] = vershini[i, positionI];

M[positionI, i] = vershini[positionI, i];

}

numelement++;

min = 100; j = 0; count = MHieght;

}

numelement++;

for (i = 0; i < MHieght; i++)

{

for (j = 0; j < MWidth; j++)

{

textBox2.Text = textBox2.Text + OSTOV[i, j] + " ";

}

textBox2.Text = textBox2.Text + "\r\n";

}

weight.Add(0);

VershX.Add(0);

VershY.Add(0);

DrawCoordinatsX.Add(0);

DrawCoordinatsY.Add(0);

j = 1;

for (i = 1; i < MHieght + 1; i++, j = 1)

{

for (j = j + i; j < MWidth + 1; j++)

{

if (OSTOV[i - 1, j - 1] != 0)

{

weight.Add(OSTOV[i - 1, j - 1]);

VershX.Add(i);

VershY.Add(j);

}

}

}

angle = 360 / MHieght;

plus = angle;

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

{

xc = 120 + (98 * Math.Cos((angle / 180D) * Math.PI));

yc = 120 + (98 * Math.Sin((angle / 180D) * Math.PI));

angle = angle + plus;

DrawCoordinatsX.Add(Convert.ToInt32(xc)); DrawCoordinatsY.Add(Convert.ToInt32(yc));

}

for (i = 1; i < VershX.Count; i++)

{

GrapWriterr.DrawLine(GP, DrawCoordinatsX[VershX[i]], DrawCoordinatsY[VershX[i]], DrawCoordinatsX[(VershY[i])], DrawCoordinatsY[VershY[i]]);

string num = Convert.ToString(weight[i]);

GrapWriterr.DrawString(num, Font2, Brushes.Black, ((DrawCoordinatsX[VershX[i]] + DrawCoordinatsX[(VershY[i])]) / 2) - 8, ((DrawCoordinatsY[VershX[i]] + DrawCoordinatsY[(VershY[i])]) / 2) - 10);

}

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

{

string num = Convert.ToString(i);

SolidElipse.FillEllipse(elipse, new System.Drawing.Rectangle(DrawCoordinatsX[i] - 13, DrawCoordinatsY[i] - 13, 26, 26));

GrapWriterr.DrawString(num, Font, Brushes.Black, DrawCoordinatsX[i] - 8, DrawCoordinatsY[i] - 10);

}

for (int i = 0; i < weight.Count; i++)

way += weight[i];

string ways;

ways = "Величина минимального остова = " + Convert.ToString(way);

TextWriterr.DrawString(ways, Font3, Brushes.Black, 300, 470);

}

public void DrawBaseGraph(int[,] Overshini)

{

System.Drawing.SolidBrush elipse = new System.Drawing.SolidBrush(System.Drawing.Color.DeepSkyBlue);

System.Drawing.Graphics SolidElipse = pictureBox2.CreateGraphics();

System.Drawing.Font Font = new System.Drawing.Font("Arial", 12);

System.Drawing.Font Font2 = new System.Drawing.Font("Arial", 16);

Graphics GrapWriterr = pictureBox2.CreateGraphics();

Pen GP = new Pen(Color.Green, 2);

double angle, plus, xc, yc;

Oweight.Add(0);

OriginVershX.Add(0);

OriginVershY.Add(0);

OriginDrawCoordinatsX.Add(0);

OriginDrawCoordinatsY.Add(0);

j = 1;

for (i = 1; i < MHieght + 1; i++, j = 1)

{

for (j = j + i; j < MWidth + 1; j++)

{

if (Overshini[i - 1, j - 1] != 0)

{

Oweight.Add(Overshini[i - 1, j - 1]) ;

OriginVershX.Add(i);

OriginVershY.Add(j);

}

}

}

angle = 360 / MHieght;

plus = angle;

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

{

xc = 120 + (98 * Math.Cos((angle / 180D) * Math.PI));

yc = 120 + (98 * Math.Sin((angle / 180D) * Math.PI));

angle = angle + plus;

OriginDrawCoordinatsX.Add(Convert.ToInt32(xc)); OriginDrawCoordinatsY.Add(Convert.ToInt32(yc));

}

for (i = 1; i < OriginVershX.Count; i++)

{

GrapWriterr.DrawLine(GP, OriginDrawCoordinatsX[OriginVershX[i]], OriginDrawCoordinatsY[OriginVershX[i]], OriginDrawCoordinatsX[(OriginVershY[i])], OriginDrawCoordinatsY[OriginVershY[i]]);

string num = Convert.ToString(Oweight[i]);

GrapWriterr.DrawString(num, Font2, Brushes.Black, ((OriginDrawCoordinatsX[OriginVershX[i]] + OriginDrawCoordinatsX[(OriginVershY[i])]) / 2) - 8, ((OriginDrawCoordinatsY[OriginVershX[i]] + OriginDrawCoordinatsY[(OriginVershY[i])]) / 2) - 10);

}

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

{

string num = Convert.ToString(i);

SolidElipse.FillEllipse(elipse, new System.Drawing.Rectangle(OriginDrawCoordinatsX[i] - 13, OriginDrawCoordinatsY[i] - 13, 26, 26));

GrapWriterr.DrawString(num, Font, Brushes.Black, OriginDrawCoordinatsX[i] - 8, OriginDrawCoordinatsY[i] - 10);

}

}

}

}



Приложение B. Результат работы программы

При вводе данной матрицы:

приложение выводит следующие данные (рис.11):

Рисунок 11 - Результат работы программы

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

...