1. Для всех пар полного подграфа считываем длины соединяющих их рёбер.
. Упорядочиваем рёбра по возрастанию их длин.
. Последовательно просматриваем упорядоченное множество рёбер, соединяем вершины теми рёбрами, которые не образуют цикла с рёбрами, уже вошедшими в дерево
Блок-схема алгоритма представлена на рисунке 3.
Рис.3 Укрупненная блок-схема разрабатываемого алгоритма
Развёрнутая блок-схема алгоритма
· Укрупненная блок-схема программы представлена на рисунке 4.1
Рис.4.1 Укрупненная блок-схема программы
· Схема алгоритма заполнения массива ребер представлена на рисунке 4.2
Рис.4.2 Схема алгоритма заполнения массива ребер
Схема алгоритма сортировки ребер по возрастанию их длин представлена на рисунке 4.3
Сортировка массива ребер происходит методом пузырьковой сортировки.
Рис.4.3 Схема алгоритма сортировки
· Схема алгоритма Краскала построения КС дерева представлена на рисунке 4.4
Рис.4.4 Схема алгоритма Краскала построения КС дерева
Контрольный примера
Требуется построить КСД для цепи содержащей 6 контактов. Полный граф на рис:
Рис.5 Полный граф
Пусть матрица длин ребер графа цепи имеет вид:
U= 
n = 6; n*(n-1) = 15
. Упорядочивание длин ребер полного графа
- 15 элементов.
. Включаем в 
в дерево получаем 1-ую изолированную компоненту связности.
. Включаем в дерево 
, получаем 2-ую изолированную компоненту связности (2,3).
. Включаем 
- получаем 3-ю изолированную компоненту связности (4,5).
. Включаем 
- получаем 4-ю изолированную компоненту связности (1,6,4,5).
Ребро 
образовывает цикл - брать нельзя.
Ребро 
тоже образовывает цикл - брать нельзя.
|
|
. Включаем в дерево 
. КСД построено.
Примечание: цикл образуется тогда, когда обе вершины включаемого ребра принадлежат одной компоненте связности
Недостатки:
) Необходимо на каждом шаге проверять условия необразования цикла, а так же наблюдение за различными компонентами связности.
) Большое время уходит на упорядочивание ребер полного графа.
Перечень идентификаторов
type
RBR=record
x1,x2:integer; {Начальная и конечная вершины ребра}
ves:integer; {Вес ребра}
rebro:array of RBR; {Массив ребер}
trassa:array of RBR; {Массив ребер, включенных в КС дерево}:array of integer; {Массив вершин, включенных в дерево}:boolean; {Логическая переменная, определяющая, входит ли вершина в массив вершин, включенных в дерево}, trassaLen, rebroLen:integer; {Длины стока, массива ребер, включенных в дерево, массива ребер}
i, j, k:integer; {Счетчики цикла}:string; {Упорядоченный список ребер}: string; {Список ребер, включенных в дерево}
Текст программы
Unit1;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, Grids, StdCtrls, ComCtrls;=record,x2:integer;:integer;;= class(TForm): TGroupBox;: TLabel;: TEdit;: TStringGrid;: TButton;: TButton;: TButton;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;Edit1KeyUp(Sender: TObject; var Key: Word;: TShiftState);Button1Click(Sender: TObject);Button3Click(Sender: TObject);Button2Click(Sender: TObject);
{ Private declarations }
{ Public declarations };: TForm1;:array of RBR;:array of RBR;:array of integer;,trassaLen:integer;,j,k,rebroLen:integer;:boolean;
{$R *.dfm}TForm1.Edit1KeyUp(Sender: TObject; var Key: Word;: TShiftState);: integer;Edit1.Text='' then Edit1.Text:='0';:=StrToInt(Edit1.Text);.ColCount:=num;.RowCount:=num;;TForm1.Button1Click(Sender: TObject);,j: integer;.Visible:=false;.Caption:='';.Visible:=false;.Visible:=false;.Caption:='';.Visible:=false;.Text:='0';i:=0 to stringgrid1.ColCount-1 doj:=0 to stringgrid1.RowCount-1 do.Cells[i,j]:='';.ColCount:=1;.RowCount:=1;;TForm1.Button3Click(Sender: TObject);;;TForm1.Button2Click(Sender: TObject);,q,k,l,Dlina:integer;:RBR;,j:integer;:string;:integer;: string;:=0;:=0;i:=0 to Strtoint(edit1.text)-1 do beginj:=0 to Strtoint(edit1.text)-1 do(i<j) and (Stringgrid1.cells[i,j]<>'0') then begin:=rebroLen+1;(rebro,rebroLen);[k].x1:=i+1;[k].x2:=j+1;[k].Ves:=Strtoint(Stringgrid1.cells[i,j]);:=k+1;;;end;i:=0 to k-1 doj:=0 to k-i-2 dorebro[j].Ves>rebro[j+1].Ves then:=rebro[j];[j]:=rebro[j+1];[j+1]:=buf;;:='';i:=0 to k-1 do:=put+' '+'X'+inttostr(rebro[i].x1)+'X'+inttostr(rebro[i].x2)+'('+inttostr(rebro[i].Ves)+')';(put);:=2;(stock,2);[0]:=rebro[0].x1;[1]:=rebro[0].x2;:=1;(trassa,1);[0]:=rebro[0];i:= 1 to length(rebro)-1 do:=0;:=false;k<>stockLen dorebro[i].x2=stock[k] then inSt:=true;:=k+1;;inSt=false then
|
|
//rebro[i].Fl:=true;
//добавление нового в сток:=stockLen+1;
setlength(stock,stockLen);[stockLen-1]:=rebro[i].x2;
//составление рёбер:=trassaLen+1;(trassa,trassaLen);[trassaLen-1]:=rebro[i];
//поменяем вершины местами:=0;:=false;k<>stockLen dorebro[i].x1=stock[k] then inSt:=true;:=k+1;;inSt=false then:=rebro[i].x1;[i].x1:=rebro[i].x2;
rebro[i].x2:=p;
//добавление нового в сток
stockLen:=stockLen+1;(stock,stockLen);[stockLen-1]:=rebro[i].x2;
//составление рёбер:=trassaLen+1;(trassa,trassaLen);[trassaLen-1]:=rebro[i];;;;.Visible:=true;.Visible:=true;.Visible:=true;:=0;:='';i:= 0 to length(trassa)-1 do:=Dlina+trassa[i].Ves;:=tr+' | '+inttostr(trassa[i].x1)+'--'+inttostr(trassa[i].x2)+' | ';.Caption:=' - '+tr+' -';.Caption:='Dlina = '+inttostr(Dlina);
end;.