Алгоритмы на графах

Выходные  значения – координаты вершин и  смежных им ребер составляющих минимальный маршрут между двумя заданными вершинами.

void __fastcall TForm3::Button5Click(TObject *Sender){}

Функция очистки компонентов Image1, edit3, edit4, edit5.

Image1->Canvas->Pen->Color=clWhite – устанавливаем белый цвет пера

Image1-> Canvas->Brush->Color = clWhite; - устанавливаем белую заливку

Edit5->Clear() – удаляем весь текст из поля ввода edit5

Image1->Canvas->FillRect(Rect(0,0,Image1->Width,Image1->Height)) – рисуем белый прямоугольник по всей площади компонента и заливаем его.

Edit4->Clear() – удаляем весь текст из поля ввода edit4

Edit3->Clear()  – удаляем весь текст из поля ввода edit3

Входные данные  - компоненты Image1, edit4, edit5

Данная  функция не возвращает значений

 

void __fastcall TForm3::Button6Click(TObject *Sender){}

Данная  функция предназначена для очистки  компонента Image2

Image2->Canvas->Pen->Color=clWhite - устанавливаем белый цвет пера

Image2-> Canvas->Brush->Color = clWhite -  устанавливаем белую заливку

Image2->Canvas->FillRect(Rect(0,0,Image1->Width,Image1->Height)) - рисуем белый прямоугольник по всей площади компонента и заливаем его.

Входные данные  - компонент Image2

Данная  функция не возвращает значений

 

void __fastcall TForm3::Button3Click(TObject *Sender){}

Функция предназначена для открытия текстового файла help.docx. используется стандартная  функция

ShellExecute(Handle, "open", "help.docx", NULL, NULL, SW_NORMAL);

 

void __fastcall TForm3::Button1Click(TObject *Sender){}

Объект  класса Tprinter – Prntr соответствует запросу на печать через локальный принтер (установленный на компьютере по умолчанию!!!) Prntr->BeginDoc() – открываем сессию печати.

Prntr->Canvas->Draw(10,10, Image1->Picture->Graphic) –задаём положение картинки на листе и указываем на компонент из которого необходимо напечатать изображение. Prntr->EndDoc() – закрываем сессию печати.

В

 

 

 

4. Руководство пользователя

 

 

Для установки приложения KursGrath необходимо запустить файл setup.exe для инсталяции программы на компьютер. После установки приложения пользователю нужно запустить установленное приложение KursGrath.exe. При запуске открывается главная форма программы. На ней расположены кнопки «Открыть», «Печать», «Справка», «Кратчайший путь», «Минимальный остов».

Рис.7 Главная форма

Для импортирования изображения графа  в программу, пользователю необходимо нажать кнопку «Открыть» и в диалоговом окне выбрать файл с расширением .txt, в котором содержится матрица смежности. По данным из загруженной матрицы смежности строятся 2 одинаковых графа. Первое изображение графа будет использоваться для отображения на нём кратчайшего пути между двумя, заданными пользователем, вершинами. Второе – для отображения минимального остовного дерева этого графа.

Рис.8 Прорисовка графов по матрице  смежности

  Для нахождения кратчайшего пути, пользователю предлагается ввести  номер первой вершины в поле  «Начальная вершина», и второй – в поле «Конечная вершина», затем нажать кнопку «Кратчайший путь». Результаты вычисления кратчайшего пути отобразятся на левом изображении графа(Рис.9).

 

Рис.9 Построение минимального пути

Чтобы построить минимальное остовное дерево графа, пользователю нужно нажать кнопку «Минимальный остов». Результаты вычисления отобразятся в правом изображении графа.

Рис.10 Построение минимального остовного дерева

Чтобы очистить все заполненные поля и  изображения графа, пользователь может  нажать кнопку «Clear All». Кнопка «Clear All» под левым изображением графа очищает текстовые поля «Начальная вершина» и «Конечная вершина», а также левое изображение графа. Чтобы очистить изображение графа с правой стороны формы пользователь должен нажать кнопку «Clear All» под ним.

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

Заключение

 

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

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

 

1.Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Introduction to Algorithms» . Под ред. И. В. Красикова — 2-е изд. — М.: Вильямс, 2005. -1296 с.

2. Окулов С.М. Программирование в алгоритмах М.: БИНОМ. Лаборатория знаний, 2004 г. - 341 стр.

3.Новиков Ф.А. Дискретная математика для программистов – СПб.: Питер, 2002 год. – 420 стр.

4. Кнут Д. Искусство программирования  для ЭВМ. т.1,2,3, Сортировка и поиск. - М.: Мир,.

 

 

 

 

Приложение А

Схема программной  реализации алгоритма Дейкстры

Схема программной  реализации алгоритма Прима

Приложение Б

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

 

Файл KursGrath.h

 

#ifndef KursGrathsH

#define KursGrathsH

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

#include <Classes.hpp>

#include <Controls.hpp>

#include <StdCtrls.hpp>

#include <Forms.hpp>

#include <ExtCtrls.hpp>

#include <Dialogs.hpp>

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

class TForm3 : public TForm

{

__published: // IDE-managed Components

TLabel *Label2;

TButton *Button2;

TImage *Image1;

TButton *Button4;

TImage *Image2;

TButton *Button5;

TButton *Button6;

TEdit *Edit3;

TButton *Button7;

TLabel *Label5;

TLabel *Label6;

TEdit *Edit4;

TEdit *Edit5;

TOpenDialog *OpenDialog1;

TSaveDialog *SaveDialog1;

TPrintDialog *PrintDialog1;

TPrinterSetupDialog *PrinterSetupDialog1;

TButton *Button1;

TButton *Button3;

 

void __fastcall Button5Click(TObject *Sender);

void __fastcall Button2Click(TObject *Sender);

void __fastcall Button4Click(TObject *Sender);

void __fastcall Button6Click(TObject *Sender);

void __fastcall Button7Click(TObject *Sender);

void __fastcall Button1Click(TObject *Sender);

void __fastcall Button3Click(TObject *Sender);

private: // User declarations

public:  // User declarations

__fastcall TForm3(TComponent* Owner);

};

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

extern PACKAGE TForm3 *Form3;

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

#endif 

 

Файл KursGrath.cpp

#include <vcl.h>

#pragma hdrstop

#include "KursGraths.h"

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

#include <stdio.h>

#include <math.h>

#include <fstream.h>

#include <string.h>

#pragma package(smart_init)

#pragma resource "*.dfm"

using namespace std;

TForm3 *Form3;

FILE *fout;

AnsiString name;

int n=0,l,count=0,i,j;int index = 0,p, q;

bool **data ;

int **a;

int *z;

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

__fastcall TForm3::TForm3(TComponent* Owner)

: TForm(Owner)

{

}

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

 

void __fastcall TForm3::Button5Click(TObject *Sender)

{

Image1->Canvas->Pen->Color=clWhite;

Image1-> Canvas->Brush->Color = clWhite;

Edit5->Clear();

Image1->Canvas->FillRect(Rect(0,0,Image1->Width,Image1->Height));

Edit4->Clear();

Edit3->Clear();

}

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

 

void __fastcall TForm3::Button2Click(TObject *Sender)

{

OpenDialog1->Execute();

name=OpenDialog1->FileName;

if ((fout=fopen(name.c_str(),"rb"))==NULL)

  {

  Application->MessageBox("No file", NULL, MB_OK);

  exit(1);

  }

  //fout=fopen("read.txt","r");

 fscanf(fout,"%d",&n);

 

int **a=new int *[n];

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

   {

   a[i]=new int[n];

   }

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

   {

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

a [i][j]=0;}  }

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

   {

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

fscanf(fout,"%d", &a[i][j]);

   }

   Image1->Canvas->Pen->Color=clBlack;

   Image1->Canvas->Pen->Width=3;

 for (int t = 0; t < n; t++){

for (int q = 0; q < n; q++){

if (a [t][q] != 0){

   Image1->Canvas->MoveTo(215+(130*cos(t*2*3.14/n)),154+(130*sin(t*2*3.14/n)));

  Image1->Canvas->LineTo(215+(130*cos(q*2*3.14/n)),154+(130*sin(q*2*3.14/n)));

  Image1->Canvas->TextOutA((215+(130*cos(t*2*3.14/n))+215+(130*cos(q*2*3.14/n)))/2, ((154+(130*sin(t*2*3.14/n)))+(154+(130*sin(q*2*3.14/n))))/2,a[t][q]);

}}}

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

   Image1->Canvas->Pen->Color=clRed;

Image1->Canvas->Ellipse(200+(130*cos(i*2*3.14/n)),(174+(130*sin(i*2*3.14/n))), 200+(130*cos(i*2*3.14/n))+40, 174+(130*sin(i*2*3.14/n))-40);

Image1->Canvas->TextOutA(225+(130*cos(i*2*3.14/n))-8, 144+(130*sin(i*2*3.14/n))+2,i+1);

}

   Image2->Canvas->Pen->Color=clBlack;

   Image2->Canvas->Pen->Width=3;

 for (int t = 0; t < n; t++){

for (int q = 0; q < n; q++){

if (a [t][q] != 0){

   Image2->Canvas->MoveTo(215+(130*cos(t*2*3.14/n)),154+(130*sin(t*2*3.14/n)));

  Image2->Canvas->LineTo(215+(130*cos(q*2*3.14/n)),154+(130*sin(q*2*3.14/n)));

  Image2->Canvas->TextOutA((215+(130*cos(t*2*3.14/n))+215+(130*cos(q*2*3.14/n)))/2, ((154+(130*sin(t*2*3.14/n)))+(154+(130*sin(q*2*3.14/n))))/2,a[t][q]);

}}}

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

   Image2->Canvas->Pen->Color=clRed;

Image2->Canvas->Ellipse(200+(130*cos(i*2*3.14/n)),(174+(130*sin(i*2*3.14/n))), 200+(130*cos(i*2*3.14/n))+40, 174+(130*sin(i*2*3.14/n))-40);

Image2->Canvas->TextOutA(225+(130*cos(i*2*3.14/n))-8, 144+(130*sin(i*2*3.14/n))+2,i+1);

}

fclose(fout);

}

 

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

 

void __fastcall TForm3::Button4Click(TObject *Sender)

{

int mas[3] [20];

int kmas=0;

int versh[20];

 

if ((fout=fopen(name.c_str(),"rb"))==NULL)

  {

  Application->MessageBox("No file", NULL, MB_OK);

  exit(1);

  }

fscanf(fout,"%d",&n);

 

int **a=new int *[n];

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

   {

   a[i]=new int[n];

   }

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

   {

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

a[i][j]=0;}  }

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

   {

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

fscanf(fout,"%d", &a[i][j]);

   }

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

   {

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

  if(a[i][j]==0) {a[i][j] = 1000;}}

   }

 

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

versh[i]=0;

versh[1]=1;

 

 

int k=n-1;

int sum=0;

while (k!=0)

{

int buf=1000;

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

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

{

if ((a[i][j] < buf) && ((versh[i]==1) || (versh[j]==1)) && (versh[i]!=versh[j]))

{buf=a[i][j]; p=i; q=j;}

}

if (versh[p]==1) versh[q]=1; else versh[p]=1;

a[p][q]=1000;

mas[0] [kmas]=p;

mas[1] [kmas]=q;

mas[2] [kmas]=buf;

sum=sum+buf;

kmas++; k--;

}

int x2[20]; for (int i=0; i<n; i++) {x2[i]=0;}

int y2[20];  for (int i=0; i<n; i++) {y2[i]=0;}

Image2->Canvas->Pen->Color=clGreen;

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

{

x2[i]=215+(130*cos(i*2*3.14/n));

y2[i]=154+(130*sin(i*2*3.14/n));

}

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

{

Image2->Canvas->MoveTo (x2[mas[1] [i]], y2[mas[1] [i]]);

Image2->Canvas->LineTo (x2[mas[0] [i]], y2[mas[0] [i]]);

}

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

 

Image2->Canvas->Ellipse(x2[i]-15,y2[i]-20,x2[i]+25,y2[i]+20);

Image2->Canvas->TextOutA(x2[i]+2,y2[i]-8,i+1);}

 fclose(fout);

  ShowMessage("Суммарный вес пути - " + IntToStr(sum)) ;

}

 

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

 

void __fastcall TForm3::Button6Click(TObject *Sender)

{

Image2->Canvas->Pen->Color=clWhite;

Image2-> Canvas->Brush->Color = clWhite;

Image2->Canvas->FillRect(Rect(0,0,Image1->Width,Image1->Height));

}

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

 

void __fastcall TForm3::Button7Click(TObject *Sender)

{

AnsiString buf,m; int l, k=0,mass[10];

int infinity=1000, n, v;                     // Бесконечность

  if ((fout=fopen(name.c_str(),"rb"))==NULL)

  {

  Application->MessageBox("No file", NULL, MB_OK);

  exit(1);

  }

fscanf(fout,"%d",&n);

 

bool **data=new bool *[n];

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

   {

   data[i]=new bool[n];

   }

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

   {

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

data [i][j]=0;}  }

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

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

fscanf(fout,"%d", &data[i][j]); }

 

   int p= n;   

   int s = StrToInt(Edit4->Text)-1;                

   int g = StrToInt(Edit5->Text)-1;                

   int x[6];

   x[i]=1    int t[6]; 

   int h[6];  //h[i]

   int z[6];    

 

   int u;     

   for (u=0;u<p;u++)

   {

  t[u]=infinity;

 

  x[u]=0;       

   }

   h[s]=0;

   t[s]=0;

   x[s]=1;

   v=s;   

 

   while(1)

   {

 

  for(u=0;u<p;u++)

  {

 if(data[v][u]==0)continue;

 if(x[u]==0 && t[u]>t[v]+data[v][u])

 {

            t[u]=t[v]+data[v][u]; 

h[u]=v; 

 

}

  }

    

      int w=infinity;    

v=-1;           

  

  

      for(u=0;u<p;u++)

      {

 if(x[u]==0 && t[u]<w)

  

                              

{

            v=u;

w=t[u];

}

  }

  if(v==-1)

  {

 Application->MessageBox("Указанные вершиниы не имеют ребер", NULL, MB_OK);

 break;

  }

  if(v==g)      {       

   u=g;

   while(u!=s)

{

Edit3->Text=Edit3->Text + IntToStr(u)+ ' ';

u=h[u];

 

}

//Label3->Caption=s;

 

   break;

  }

 

  x[v]=1;

   }

Edit3->Text=Edit3->Text + IntToStr(s);

 

m = Edit3->Text;

for(l=1,buf="";l<=m.Length()+1;l++)

{

  if(l==m.Length()+1)

   {

mass[k++] = StrToInt(buf);

    break;

   }

  if(m[l]==' ')

   {

mass[k++] = StrToInt(buf);

    buf = "";

   }

  buf += m[l];

}

 int x1[20]; for (int i=0; i<n; i++) {x1[i]=0;}

int y1[20];  for (int i=0; i<n; i++) {y1[i]=0;}

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

{

x1[i]=215+(130*cos(i*2*3.14/n));

y1[i]=154+(130*sin(i*2*3.14/n));

}

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

 for (l=0; l < k-1; l++) {

 if (i==mass[l]) {

Image1->Canvas->Pen->Color=clGreen;

  Image1->Canvas->MoveTo (x1[mass[l+1]], y1[mass[l+1]]);

Image1->Canvas->LineTo (x1[mass[l]], y1[mass[l]]);

}}}

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

 for (l=0; l < k; l++) {

 if (i==mass[l]) {

Image1->Canvas->Pen->Color=clGreen;

Image1->Canvas->Ellipse(200+(130*cos(i*2*3.14/n)),(174+(130*sin(i*2*3.14/n))), 200+(130*cos(i*2*3.14/n))+40, 174+(130*sin(i*2*3.14/n))-40);

Image1->Canvas->TextOutA(225+(130*cos(i*2*3.14/n))-8, 144+(130*sin(i*2*3.14/n))+2,i+1);

}}}

 

  fclose(fout);

  ShowMessage("Длинна пути - " + IntToStr(t[g])) ;

}

 

 

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

 

void __fastcall TForm3::Button1Click(TObject *Sender)

{

 TPrinter *Prntr = Printer();

        Prntr->BeginDoc();

Prntr->Canvas->Draw(10,

10, Image1->Picture->Graphic);

 Prntr->Canvas->Draw(10,

10, Image2->Picture->Graphic);

Prntr->EndDoc();

}

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

 

 

void __fastcall TForm3::Button3Click(TObject *Sender)

{

  ShellExecute(Handle, "open", "help.docx", NULL, NULL, SW_NORMAL);

}