4577

Покрывающее дерево. Концепция алгоритма Краскала

Контрольная

Информатика, кибернетика и программирование

Алгоритм Краскала может строить дерево одновременно для нескольких компонент связности, которые в процессе решения объединяются в одно связанное дерево. Полный граф задается списком ребер. Перед работой список ребер сортируется по возрастанию длины....

Русский

2012-11-22

252.41 KB

102 чел.

Алгоритм Краскала может строить дерево одновременно для нескольких компонент связности, которые в процессе решения объединяются в одно связанное дерево.

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

Обобщённый алгоритм

Алгоритм состоит из следующей последовательности действий:

  1. Создается список ребер R, содержащий длину ребра, номер исходной вершины                                   ребра, номер конечной вершины ребра, признак включения данного ребра в дерево.
  2. Данный список упорядочивается в порядке возрастания длин ребер.
  3.  Просматривается список R и выбирается из него ребро с минимальной длиной, еще не включенное в результирующее дерево и не образующее цикла с уже построенными ребрами.
  4.  Если все вершины включены в дерево и количество ребер на единицу меньше количества вершин, то алгоритм свою работу закончил. В противном случае осуществляется возврат к пункту 3.

Заключение

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

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

Список используемых источников

  1. Рыбаков Глеб. Минимальные остовные деревья (дата обращения: 03.03.2011)
  2.  Белов Теория Графов, Москва, "Наука", 1968 (дата обращения: 05.03.2011)
  3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат, 1988 (дата обращения: 09.04.2011)


Приложение В

Блок-схема обобщённой алгоритм Краскала

Да

Упорядочение ребер по их весу

Начальное положение

Начало

Добавление минимального ребра в дерево, которое не создает цикл

Все вершины включены в дерево

Нет

Конец

Рисунок В.1 - Обобщенный алгоритм Краскала


Приложение Г

(обязательное)

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

Г.1 Введение

Г.1.1 Область применения

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

Г.1.2 Краткое описание возможностей

Программа позволяет найти минимальное покрывающее дерево, используя алгоритм Краскала. Реализована возможность визуализации графа.

Г.1.3 Уровень подготовки пользователя

Пользоваться системой должен человек с уровнем знания ПК на уровне «Пользователь», умеющий работать с Windows-приложениями.

Г.1.4 Перечень эксплуатационной документации

В перечень эксплуатационной документации, с которой необходимо ознакомиться, входят «Руководство пользователя», «Руководство программиста».

Г.2 Назначение и условия применения

Г.2.1 Виды деятельности, функции

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

Г.2.2 Программные и аппаратные требования к системе

Для использования программного продукта необходим компьютер, на котором установлена операционная система MS Windows XP / Vista / 7.

Достаточная комплектация:

  1. процессор Intel Pentium IV;
  2. объем ОЗУ 128 МБайт;
  3. объем дискового пространства 30 Mb для исполняемого файла;
  4. монитор;
  5. устройства ввода информации и управления (мышь, клавиатура);
  6.  CD-ROM или USB-разъем.

Г.3 Подготовка к работе

Г.3.1 Комплект установки

Для установки достаточно иметь папку с запускаемым файлом, которая прилагается на диске

Г.3.2 Запуск системы

Для работы с программой необходимо переместить директорию программы с CD-диска с программой на жесткий диск компьютера. Для запуска приложения «Минимальное покрывающее дерево» откройте папку, в которую была скопирована программа, и запустите файл «МПК.exe».

Г.3.3 Проверка работоспособности системы 

Программное обеспечение работоспособно, если в результате действий пользователя, изложенных в пункте Г.3.2, на экране монитора отобразилось главное окно приложения без выдачи пользователю сообщений о сбое в работе (рисунок Г.1).

Рисунок Г.1 – Окно приложения «Минимальное покрывающее дерево»

Г.4 Описание операций

Г.4.1 Наименование операций

Поиск минимального покрывающего дерева алгоритмом Крускала

Г.4.2 Условия выполнения операции

Приложение запущено, успешно функционирует, введены все данные для выполнения операции.

Г.4.3 Подготовительные действия

Ввод данных, заполнение начального состояния игрового поля.

Г.4.4 Основные действия

Необходимо заполнить матрицу смежности, изначально оно задается случайным образом. Для решения задачи нужно нажать на кнопку «Расчет» (рисунок Г.2).

Рисунок Г.2 – «Расчет»

Г.4.5 Ресурсы, расходуемые на операцию

Отсутствуют.

Г.5 Аварийные операции, восстановление 

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

При сбое в работе аппаратуры восстановление нормальной работы программы должно наступить после перезагрузки операционной системы и запуска исполняемого файла «МПК.exe»

Г.6 Рекомендации по освоению

Для успешного освоения приложения «Минимальное покрывающее дерево» необходимо иметь навыки работы с персональным компьютером на уровне «Пользователь» и изучить настоящее «Руководство пользователя». Контрольный пример работы с системой

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

  1. Запустите программу (откройте исполняемый файл «МПК.exe»). После запуска появляется главное окно приложения (рисунок Г.4).

Рисунок Г.4 – Запуск программы

  1. Задайте необходимые значения как показано на рисунке Г.5

Рисунок Г.5 – Создание вершин графа

  1. Нажмите на кнопку «Расчет».
  2. При решение выводиться изображение с минимальным покрывающим деревом (рисунок Г.6).

Рисунок Г.6 – Результат

 

 

          Приложение Д

(обязательное)

Руководство программиста

Д.1 Назначение и условия применения программы

Программа предназначена для демонстрации поиска минимального покрывающего дерева алгоритмом Крускала. 

Для использования программного продукта необходим компьютер, на котором установлена операционная система MS Windows XP / Vista / 7.

Достаточная комплектация:

  1. процессор Intel Pentium IV;
  2. объем ОЗУ 128 МБайт;
  3. объем дискового пространства 30 Mb для исполняемого файла;
  4. монитор;
  5. устройства ввода информации и управления (мышь, клавиатура);
  6.  CD-ROM или USB-разъем.

Д.2 Характеристика программы

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

Скорость работы приложения зависит от аппаратного обеспечения компьютера, на котором оно установлено.

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

Д.3 Обращение к программе

Основные модули и компоненты программы представлены в таблице Д.1.

Таблица Д.1 – Основные модули программы

Имя модуля

Назначение

Основные процедуры и функции

Unit1

Главный модуль

  1.  Procedure TForm1.Button1Click;

Обнуление матрицы смежности.

  1.  Procedure TForm1.Button3Click;

Закрытие программы.

  1.  Procedure TForm1.Button2Click;

Нахождение минимального дерева

  1.  Function IsConnectedTrue;

Проверка соединены ли вершины

  1.  Procedure SortRebra;

Сортирует ребра по их весу.

6. Procedure TForm1.Edit1KeyPress

Обрабатывает только числа введеные с клавиатуры


Д.4 Входные и выходные данные

Входные данные:

  1. Матрица смежности (тип integer)
  2. Количество вершин (тип integer)

Выходные данные:

  1. Изображение минимально дерева

Д.5 Сообщения

При попытке создания запуска алгоритма на выполнение с некорректным заполненными полями, пользователю выдаётся сообщение о ошибке заполнения:

Рисунок Д.5.1 – Сообщение о ошибке заполнения


Приложение Ж

Листинг основного модуля

unit Unit1;

interface

uses

 Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

 Dialogs, Grids, StdCtrls, ComCtrls , unit2, ExtCtrls;

type

rebro=record

x1,x2:integer;

ves:integer;

exec:boolean;

end;

tochka=record

n:integer;

used:boolean;

end;

 TForm1 = class(TForm)

   GroupBox1: TGroupBox;

   Label1: TLabel;

   Edit1: TEdit;

   StringGrid1: TStringGrid;

   Button1: TButton;

   Button2: TButton;

   Button3: TButton;

   Label2: TLabel;

   UpDown1: TUpDown;

   Label3: TLabel;

   Image1: TImage;

   Label4: TLabel;

   Image2: TImage;

   Label5: TLabel;

   Label6: TLabel;

   procedure Button1Click(Sender: TObject);

   procedure Button3Click(Sender: TObject);

   procedure Button2Click(Sender: TObject);

   procedure Edit1Change(Sender: TObject);

   procedure Edit1KeyPress(Sender: TObject; var Key: Char);

   { Private declarations }

 public

   { Public declarations }

 end;

var

 Form1: TForm1;

 rebra:array[1..100] of rebro;

 ver: array[0..20] of tochka;

//  ex: array[0..20] of integer;

//  exc,col: integer;

 N, numK:byte;

  function TryConnect():boolean;

  function IsConnected():boolean;

  function IsConnectedTrue():boolean;

  function CanConnectAll():boolean;

  procedure SortRebra();

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var

i,j: integer;

begin

Edit1.Text:='0';

For i:=0 to stringgrid1.ColCount-1 do

 For j:=0 to stringgrid1.RowCount-1 do

  StringGrid1.Cells[i,j]:='';

StringGrid1.ColCount:=1;

StringGrid1.RowCount:=1;

end;

procedure TForm1.Button3Click(Sender: TObject);

begin

Halt;

end;

procedure TForm1.Button2Click(Sender: TObject);

var k,numr,i,j:byte;

   tempb:boolean;

   dots_exec, rebra_ves: set of byte;

   MatrixX,MatrixY: array[1..20] of integer;

   fi:real;

begin

k:=0;

 // input

 for i:=0 to N-1 do  begin

 for j:=0 to i do

  if (not(i=j) and (Strtoint(Stringgrid1.cells[i,j])>0)) then

  begin

   k:=k+1;

   Rebra[k].x1:=j+1;

   Rebra[k].x2:=i+1;

   Rebra[k].ves:=Strtoint(Stringgrid1.cells[i,j]);

   Rebra[k].exec:=false;

  end;

 end;

 Image1.Picture:= nil;

fi:=pi/N;

 // risuem tochki

for i:=1 to N do

begin

MatrixX[i]:=round(120+100*cos(2*fi*i));

MatrixY[i]:=round(120+100*sin(2*fi*i));

Image1.Canvas.Ellipse(MatrixX[i],MatrixY[i],MatrixX[i]+10,MatrixY[i]+10);

Image1.Canvas.TextOut(MatrixX[i]+1,MatrixY[i]-14,inttostr(i));

end;

// rusuem linii

for i:=1 to k do begin;

//showmessage('ee'+inttostr(numr));

Image1.Canvas.MoveTo(MatrixX[rebra[i].x1]+5,MatrixY[rebra[i].x1]+5);

Image1.Canvas.LineTo(MatrixX[rebra[i].x2]+5,MatrixY[rebra[i].x2]+5);

Image1.Canvas.TextOut(round((MatrixX[rebra[i].x1]+MatrixX[rebra[i].x2])/2)-10,round((MatrixY[rebra[i].x1]+MatrixY[rebra[i].x2])/2)-10,inttostr(rebra[i].ves));

end;

  numK:=k;

  //sort

  SortRebra();

 label3.Caption:='';

 for i:=1 to k do

 label3.Caption:=label3.Caption+#13+inttostr(rebra[i].x1)+' '+inttostr(rebra[i].x2)+' - '+inttostr(rebra[i].ves);

 dots_exec:=dots_exec+[rebra[1].x1];

 dots_exec:=dots_exec+[rebra[1].x2];

 rebra_ves:=rebra_ves+[rebra[1].ves];

 numr:=1;

 rebra[1].exec:=true;

 for i:=2 to k do

  if

    ((rebra[i].x1 in dots_exec) and not(rebra[i].x2 in dots_exec))

  or

    (not(rebra[i].x1 in dots_exec) and (rebra[i].x2 in dots_exec))

   then

  begin

     numr:=numr+1;

   //showmessage('add '+inttostr(i));

     rebra[i].exec:=true;

     dots_exec:=dots_exec+[rebra[i].x1];

     dots_exec:=dots_exec+[rebra[i].x2];

     rebra_ves:=rebra_ves+[rebra[i].ves];

 end;

if not(isConnected) then

begin

  TryConnect();

end;

Image2.Picture:= nil;

fi:=pi/N;

 // risuem tochki

for i:=1 to N do

begin

MatrixX[i]:=round(120+100*cos(2*fi*i));

MatrixY[i]:=round(120+100*sin(2*fi*i));

Image2.Canvas.Ellipse(MatrixX[i],MatrixY[i],MatrixX[i]+10,MatrixY[i]+10);

Image2.Canvas.TextOut(MatrixX[i]+1,MatrixY[i]-14,inttostr(i));

end;

// rusuem linii

for i:=1 to k do

if rebra[i].exec then    begin

//showmessage('ee'+inttostr(numr));

Image2.Canvas.MoveTo(MatrixX[rebra[i].x1]+5,MatrixY[rebra[i].x1]+5);

Image2.Canvas.LineTo(MatrixX[rebra[i].x2]+5,MatrixY[rebra[i].x2]+5);

Image2.Canvas.TextOut(round((MatrixX[rebra[i].x1]+MatrixX[rebra[i].x2])/2)-10,round((MatrixY[rebra[i].x1]+MatrixY[rebra[i].x2])/2)-10,inttostr(rebra[i].ves));

end;

if CanConnectAll then

label4.Caption:='Можно соединить все точки!'

else

label4.Caption:='Нельзя соединить все точки!';

end;

procedure TForm1.Edit1Change(Sender: TObject);

var

i, j: byte;

begin

  if Edit1.Text='' then Edit1.Text:='0';

  N:=StrToInt(Edit1.Text);

  StringGrid1.ColCount:=N;

  StringGrid1.RowCount:=N;

for i:=0 to N-1 do

for j:=0 to i do

begin

StringGrid1.cells[j,i]:=inttostr(Random(10)+1);

if i=j then

Stringgrid1.cells[j,i]:='0'

else

Stringgrid1.cells[i,j]:=StringGrid1.cells[j,i];

end;

end;

procedure SortRebra();

var  Buf:rebro;

     i,j:byte;

begin

  for i:=1 to numk do

  for j:=1 to numk-1 do

   if rebra[j].Ves>rebra[j+1].Ves then

    begin

    Buf:=rebra[j];

    rebra[j]:=rebra[j+1];

    rebra[j+1]:=buf;

  end;

end;

 // соединен ли граф на самом деле

 function IsConnectedTrue():boolean;

var dots_connected: set of byte;

    k:byte;

    connected_all: boolean;

    i, j: byte;

begin

k:=numK;

   ver[1].used:=true;

   dots_connected:=[];

   dots_connected:=dots_connected+[1];

   for j:=1 to n do

   for i:=1 to k do

     if ((rebra[i].exec=true) and ((rebra[i].x1 in dots_connected) or (rebra[i].x2 in dots_connected)))

     then

     begin

       dots_connected:=dots_connected+[rebra[i].x1];

       dots_connected:=dots_connected+[rebra[i].x2];

     end;

    connected_all:=true;

    for i:=1  to n do

     if not(i in dots_connected) then

        connected_all:=false;

    result:=connected_all;

end;

// соединен ли граф полностью

function IsConnected():boolean;

var dots_connected: set of byte;

    k:byte;

    connected_all: boolean;

    i, j: byte;

begin

  if not(CanConnectAll) then

    result:=true;

    exit;

  k:=numK;

  ver[1].used:=true;

  dots_connected:=[];

  dots_connected:=dots_connected+[1];

    for j:=1 to n do

       for i:=1 to k do

           if ((rebra[i].exec=true) and ((rebra[i].x1 in dots_connected) or (rebra[i].x2 in dots_connected)))

             then

             begin

               dots_connected:=dots_connected+[rebra[i].x1];

               dots_connected:=dots_connected+[rebra[i].x2];

             end;

    connected_all:=true;

    for i:=1  to n do

     if not(i in dots_connected) then

        connected_all:=false;

    result:=connected_all;

 end;

// функция пытается соединить все точки

 function TryConnect():boolean;

var dots_connected: set of byte;

    k:byte;

    connected_all: boolean;

    i, j: byte;

begin

    if not(CanConnectAll) then

    result:=true;

    exit;

   k:=numK;

   ver[1].used:=true;

   dots_connected:=[];

   dots_connected:=dots_connected+[1];

   for j:=1 to n do

   for i:=1 to k do

     if ((rebra[i].exec=true) and ((rebra[i].x1 in dots_connected) or (rebra[i].x2 in dots_connected)))

     then

     begin

       dots_connected:=dots_connected+[rebra[i].x1];

       dots_connected:=dots_connected+[rebra[i].x2];

     end;

   for j:=1 to n do

     if not(j in dots_connected) then

         for i:=1 to k do

          if

              (

                 (rebra[i].exec=false) and

                     (

                        ((rebra[i].x1=j) and (rebra[i].x2 in dots_connected))

                        or

                        ((rebra[i].x2=j) and (rebra[i].x1 in dots_connected))

                     )

              )

           then

            begin

             dots_connected:=dots_connected+[rebra[i].x1];

             dots_connected:=dots_connected+[rebra[i].x2];

             rebra[i].exec:=true;

             break;

            end;

    result:=true;

end;

// можно ли в графе соединить все точки

 function CanConnectAll():boolean;

   var dots_connected: set of byte;

       k:byte;

       connected_all: boolean;

       i, j: byte;

   begin

       k:=numK;

       ver[1].used:=true;

       dots_connected:=[];

       dots_connected:=dots_connected+[1];

       for j:=1 to n do

       for i:=1 to k do

         if ((rebra[i].x1 in dots_connected) or (rebra[i].x2 in dots_connected))

           then

           begin

             dots_connected:=dots_connected+[rebra[i].x1];

             dots_connected:=dots_connected+[rebra[i].x2];

           end;

       connected_all:=true;

       for i:=1  to n do

         if not(i in dots_connected) then

            connected_all:=false;

       result:=connected_all;

  end;

  procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: Char);

begin

if not (Key in ['0'..'9']) then

 begin

   Key := #0;

   ShowMessage('Недопустимый элемент!');

 end;

end;

end.


 

А также другие работы, которые могут Вас заинтересовать

47464. Решение геометрических задач, как средство развития самостоятельности мышления учащихся 134 KB
  Они должны не просто знакомиться с теорией предмета а видеть источники возникновения и практическую целесообразность изучения этих вопросов не просто решать задачу указанную учителем приобретая нужные навыки и умения а рассматривать условия в которых возникают задачи данного типа. Решение математических задач приобретает единую учебнопознавательную направленность в том случае когда оно реализует решение одной и той же дидактической задачи изучения математической закономерности на основе анализа частных случаев. Первые описываются...
47465. СТРАТЕГІЧНЕ УПРАВЛІННЯ. НАВЧАЛЬНИЙ ПОСІБНИК 1.01 MB
  Розглянуто основні питання стратегічного управління: сучасна концепція стратегічного управління; види стратегій підприємства; формування стратегічного набору; форми та методи забезпечення стратегічного управління. 2004 ВСТУП Ринкова економіка формує нові вимоги до підприємства що обумовлюються не тільки наявністю конкуренції та високими вимогами до якості товарів але й необхідністю гнучко реагувати на зміни ринкової ситуації яка не завжди сприяє процвітанню підприємства. Успіх підприємства залежить від здатності передбачати й змінювати...
47466. Питання для іспиту «Митне право україни» 641.5 KB
  Керівництво збиранням прикордонного мита: евеки вивізне та інфуки ввізне мито за часи Богдана Хмельницького покладалося на Державний скарб як тоді називалася фінансовобанківська служба України. Верховна Рада прийняла Закон України Про митну справу в Україні який проголосив що Україна як суверенна держава самостійно створює власну митну систему і здійснює митну справу. Верховна Рада України прийняла Постанову про створення Державного митного комітету України як центрального митного органу України та перший Митний кодекс України.
47467. Політекономія. Тарнавський М.П, Навчально-методичний посібник 2.54 MB
  Ця наука вивчає ринкову поведінку людей при використанні обмежених ресурсів виробництва що породжує за умов приватної власності економічну конкуренцію між ними. Другий факт: економічні ресурси засоби для виробництва благ обмежені. Задоволення їх обмежено рідкістю ресурсів для виробництва засобів їх задоволення. Непрямі інструментні чи виробничі використовуються для виробництва прямого блага.
47468. СТРАХОВІ ПОСЛУГИ. ПІДРУЧНИК 55.64 MB
  У підручнику розкриваються основи теорії страхових послуг та особливості різних видів страхування що реалізуються на страховому ринку України. Зміст підручника відповідає типовій програмі навчальної дисципліни Страхові послуги що дозволяє сформувати у студентів сучасні знання щодо сутності страхової послуги як специфічного товару страхового ринку умов та правил здійснення основоположних класичних і сучасних видів страхування. Порядок укладання та ведення страхової угоди 33 Сутність договору...
47469. Політологія. Конспект лекцій 243 KB
  Життя Поняття і функції політичної влади Політична та державна влади Умови ефективного функціонування політичної влади Основні концепції влади Проблема формування і функції влади в Україні. Легітимність влади криза легітимності та засоби її вирішення Демократія форма пол. Загальне визначення предмета політології можна було б запропонувати таке: політологія у більш вузькому розумінні загальна теорія політики вивчає специфічну групу закономірностей відносин соціальних суб'єктів з приводу влади. поперше спеціально досліджує політику як...
47470. ФІНАНСОВА ДІЯЛЬНІСТЬ СУБ'ЄКТІВ ПІДПРИЄМНИЦТВА 6.79 MB
  У посібнику розглянуті актуальні питання розвитку фінансової діяльності суб'єктів підприємництва в Україні організація фінансової діяльності суб'єктів підприємництва фінансування управління власним і позичковим капіталом фінансовими інвестиціями оцінка вартості підприємства фінансовий контролінг. ФОРМУВАННЯ ВЛАСНОГО КАПІТАЛУПІДПРИЄМСТВА 124 3. Власний капітал підприємства: функції складові таоцінка 124 З Формування статутного капіталу акціонерних товариств 130 Статутний капітал товариств з...
47471. Стратегічне управління 243 KB
  підприєствах Виділення стратегічних зон господарювання Зони стратегічних ресурсів Групи стратегічного впливу Класифікація методів аналізу стратегічних альтернатив Механізм ринкової конкуренції сутність характерні риси сучасного конкурентного середовища аналіз конкуренції в галузі детермінанти конкурентної переваги країни Національний ромб Аналіз конкурентного становища підприємства стратегічна сегментація зовнішнього середовища підприємства вибір позиції в конкуренції діагностика стану підприємства в конкурентному середовищі...