Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Нахождение минимального остового дерева(алгоритм Краскала)

Автор: nblazhko 17.05.2008 2:46

Вот что я смог сделать но она выводит вершины не правельно, подскажите плиз


Program Algorithm_PrimaKrascala;
Uses Crt;
Const MaxSize =100;
Infinity =1000;
Var Matrix: array[1..MaxSize, 1..MaxSize] of integer;
Color: array[1..MaxSize] of integer;
Ribs: array[1..MaxSize] of record
a, b: integer;
end;
n, a, b, k, col, i, len: integer;

Procedure Init;
Var f: text;
i, j: integer;
Begin
Assign(f, 'INPUT.MTR');
Reset(f);
Readln(f, n);
For i:=1 to n do
Begin
For j:=1 to n do read(f, matrix[i, j]);
Readln(f)
End;
For i:=1 to n do color[i]:=i;
len:=0
End;

Procedure Findmin(var a, b: integer);
Var min, i, j: integer;
Begin
min:=infinity;
For i:=1 to n-1 do
For j:=i+1 to n do
If (Matrix[i, j]<>color[j]) then
Begin
min:=Matrix[i, j];
a:=i;
b:=j
End;
len:=len+min
end;

Begin
Clrscr;
Init;
For k:=1 to n-1 do
Begin
Findmin(a, b);
Ribs[k].a:=a;
Ribs[k].b:=b;
col:=Color[b];
For i:=1 to n do
If color[i]=col then color[i]:=color[a];
End;
For i:=1 to n-1 do
Writeln(ribs[i].a, ' -', ribs[i].b);
Writeln('Length= ', len);
Readkey
End.



Matrix - матрица расстояний, значение пересечении i-ой строки и j-го столбца равно расстоянию между i-ой и j-ой вершинами. Если такого ребра нет то значение равно Infinity - просто большому числу
Color - массив цветов вершин;
Ribs - в этом массиве запоминаются найденные ребра;
a, b - вершины, соединяемые очередным минимальным ребром
len - длина дерева.
Матрицу расстояний будем хранить в текстовом файле INPUT.MTR, где число на первой строке - количество вершин n, а остальные n строк по n чисел в каждой - матрица расстояний. Если расстояние равно 1000 (Infinity), то такого ребра нет.