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.


 

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

29474. Накочередующиеся ряды, признак Лейбница 18.25 KB
  Теорема Лейбница о сходимости знакочередующихся рядов Признак Лейбница признак сходимости знакочередующегося ряда установлен Готфридом Лейбницем. Формулировка теоремы: Пусть для знакочередующегося ряда выполняются следующие условия: монотонное убывание. Тогда этот ряд сходится.
29476. ЧЕЛОВЕК ПРИСПОСОБЛЕННЫЙ 152.5 KB
  Проблема приспособления человека к изменившейся социальной среде становится предельно острой и общезначимой в условиях крутых общественных переломов когда практически все общественные слои и группы оказываются перед выбором вынужденного приспособления или самораспада. период перестройки общества и человека оказался более долгим располагал более массированными средствами включая тотальный террор и последствия двух мировых войн притом объектом воздействия оказывался расшатанный ранее тип социального человека. Ориентируясь на идеологию...
29477. ЧЕЛОВЕК НЕДОВОЛЬНЫЙ: ПРОТЕСТ И ТЕРПЕНИЕ 114.5 KB
  Чтобы преодолеть видимый парадокс нужно определить те социальные условия и структуры которые формируют и поддерживают такое сочетание а точнее взаимодействие недовольства и терпения в обществе. или к неэффективности современного социального недовольства фонового констатируют бесспорные факты но не объясняют их. Состояние общественно значимого недовольства возникает как реакция на сравнение то ли с лучшим по крайней мере более спокойным прошлым то ли с неосуществленным светлым будущим точнее с иллюзией такого будущего...
29478. ЧЕЛОВЕК ЛУКАВЫЙ: ДВОЕМЫСЛИЕ ПО-РОССИЙСКИ 150 KB
  Он приспосабливается к социальной действительности ища допуски и лазейки в ее нормативной системе то есть способы использовать в собственных интересах существующие в ней правила игры и в то же время что не менее важно постоянно пытаясь в какойто мере обойти эти правила. Успех этой системы на долгие десятилетия по крайней мере был бы невозможен если бы она опиралась только на массовое принуждение и массовый обман. Практическое отсутствие общеобязательных авторитетов создает многополярную структуру нормативного поля где...
29479. «ЧЕЛОВЕК ОГРАНИЧЕННЫЙ»: УРОВНИ И РАМКИ ПРИТЯЗАНИЙ 107.5 KB
  Стабильность притязаний На протяжении ряда лет данные ВЦИОМ охватывают как реальные так и воображаемые приписанные показатели положения человека: данные о полученном и желаемом нормальном по мнению опрошенных доходе и т. При этом 72 опрошенных считали что они получают намного меньше или несколько меньше чем заслуживают; 19 что они получают столько сколько заслуживают; 8 что получают больше чем того заслуживают. Если бы в распоряжении опрошенных исследование типа Мониторинг март 1997 г. При сходной формулировке...
29480. НАШИ ДЕСЯТЬ ЛЕТ: ИТОГИ И ПРОБЛЕМЫ (околоюбилейные размышления) 128 KB
  было подписано Постановление Президиума ВЦСПС и Госкомтруда СССР О создании Всесоюзного центра изучения общественного мнения по социальноэкономическим вопросам формальная дата появления на свет ВЦИОМ. Первое десятилетие жизни и работы ВЦИОМ можно рассматривать под разными углами зрения перебирать опросы отчеты оценивать кадры вспоминать конфликты и т. Что такое ВЦИОМ Условия и время создания нашего центра естественно наложили свой отпечаток на характер ВЦИОМ как организации или даже как своеобразного организма. Вопервых...
29481. Общественные перемены и общественное мнение 23 KB
  Человек политический: сцена и роли переходного периода 9. Человек толпа и масса в общественном мнении 17. Средний человек: фикция или реальность 19. Советский человек пять лет спустя: 1989–1994 гг.
29482. ОТ МНЕНИЙ К ПОНИМАНИЮ 90 KB
  Москва 2000 ОТ АВТОРА В книге собраны статьи публиковавшиеся в журнале Мониторинг общественного мнения1 с 1993 по 2000 гг. В этой формуле выражен один из основных принципов работы нашего центра: использовать данные изучения общественного мнения для понимания процессов и перемен в социальной экономической политической и культурной жизни общества. ВЕКТОРЫ ПЕРЕМЕН: СОЦИОКУЛЬТУРНЫЕ КООРДИНАТЫ ИЗМЕНЕНИЙ Уровни и предмет анализа в социальном исследовании Результаты массовых опросов общественного мнения как зарубежные так и отечественные чаще...