4577

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

Контрольная

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

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

Русский

2012-11-22

252.41 KB

97 чел.

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

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

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

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

  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.


 

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

14899. Заманауи тұлғалардың ислам дінін қабылдау себептері 50.5 KB
  Мұртаза БҰЛҰТАЙФилософия ғылымдарының кандидатыДінтанушы мәдениеттанушыЗАМАНАУИ ТҰЛҒАЛАРДЫҢ ИСЛАМДIНIН ҚАБЫЛДАУ СЕБЕПТЕРI [1]Ғылым және информация ғасыры деп аталған өткен жүз жылда дамыған мемлекеттердiң азаматтарынан бек көп адам ислам дiнiн өз еркiмен қабылдаған. Ол...
14900. Ислам - әлемдегі бейбітшіліктің кепілі 103.5 KB
  Мұртаза БҰЛҰТАЙФилософия ғылымдарының кандидатыДінтанушы мәдениеттанушыИСЛАМ ӘЛЕМДЕГІ БЕЙБIТШIЛIКТIҢ КЕПIЛI[1]Өткен жолғы Ислам және өркениет газеті №4 Сәуір 2001 ж. Дiни экстремизм мен терроризм деп аталатын мақаламда хақ дін исламның Батыс елдерінде пайда болған әл...
14901. Ислам дініндегі хош көрушілік 79.5 KB
  Мұртаза БҰЛҰТАЙ ҚР Білім қайраткерлері одағының мүшесі ИСЛАМ ДIНIНДЕГI ХОШКӨРУШIЛIК Дін деген ұғымның негізінде зорлықзомбылық болмауы керек бұл хақ діннің ғайрихақ хақ емес діндерден ажырасатын айқын парқы. Дін дегеніміз негізінде иман яғни сенім жататын рух...
14902. Ислам 68 KB
  Мұртаза БҰЛҰТАЙФилософия ғылымдарының кандидатыДінтанушы мәдениеттанушыИСЛАМ [1]Жаратушы ұлық тәңiр Аллаһ Тағалаға иманды және мойынсұнуды бiлдiретiн нағыз бiртәңiрлi монотеист тәухид нанымы негiзiнде пайғамбарымыз Мұхаммед Абдұллаһұлы с.а.у. 569632 тарапынан 609632 жылда
14903. Исламтану және ислам философиясы 95 KB
  Мұртаза БҰЛҰТАЙ Философия ғылымдарының кандидатыДінтанушы мәдениеттанушы ИСЛАМТАНУ Тәухид нанымы негiзiндегi ислам дiнi уә мәдениетiн әдебиетi уә өркениетiн зерттейтiн ғылымдардың жыйынтық аты. Аллаһ Тағалаға тәсiлiм болу берiлу мойынсұну; сәлеметтiлiкте һәм бейбiтшiлiк
14904. ҚАЗАҚСТАНДАҒЫ ДІН ЖӘНЕ МЕМЛЕКЕТ ҚАТЫНАСТАРЫ 68.5 KB
  ҚАЗАҚСТАНДАҒЫ ДІН ЖӘНЕ МЕМЛЕКЕТ ҚАТЫНАСТАРЫ[1]Тәуелсіздік жылдарында елімізде орын алған күрделі саясиэкономикалық жаңарулар мен өзгерулер ағымында мемлекет билігінің қайнар көзі болып табылатын халқымыздың рухани өмірі мен діни көзқарастары да бір жағынан толығып
14905. ҚҰРАНДЫ ТҮСІНУ 69.5 KB
  ҚҰРАНДЫ ТҮСІНУ Құран Кәрім Жаратушы тарапынан күллі адамзатқа және өзінен кейінгі замана атаулыға жіберілген ұқсасы жоқ қасиетті кітап. Құран – ислам дінінің бастауы бірегей бұлағы. Исламды түсіну үшін Құранды түсіну шарт. Құранды түсінбеген адам исламды да толықтай түс...
14906. ТАРАЗ ─ МҰСЫЛМАН ӨРКЕНИЕТІНІҢ ОРТА АЗИЯДАҒЫ ОРТАЛЫҒЫ 54 KB
  ТАРАЗ ─ МҰСЫЛМАН ӨРКЕНИЕТІНІҢ ОРТА АЗИЯДАҒЫ ОРТАЛЫҒЫ М.А. Утеуов М.С. Бегілдаева Тараз мемлекеттік педагогикалық институты жанындағы Кіші Ғылым Академиясы Жамбыл облыстық €œДарын€ мектепинтернаты Тараз қ. Тараз қазіргі жыл санауымыздан бұрынғы 4241 жылдары Т...
14907. ТҮРКIЛЕРДIҢ ИСЛАМ ТАРИХЫ ЖӘНЕ МӘДЕНИЕТIНДЕГI ЕРЕКШЕ ОРНЫ 72 KB
  ТҮРКIЛЕРДIҢ ИСЛАМ ТАРИХЫ ЖӘНЕ МӘДЕНИЕТIНДЕГI ЕРЕКШЕ ОРНЫ Исламият алып елдердің мәселен Әмәуи 66-1750 Аббаси 751-1258 Селжүк 1040-1157 Осман 1299-1922 патшалықтары сықылды әлемдiк мемлекеттердің ресми дiнi болған дәуiрде азат етiлген немесе олжаланған өңiрлердiң тұрғындарын жа...