Реферат: Aлгоритмы на графах

Для реализации алгоритма понадобятся:

Matrix – матрица расстояний, значение пересечении i-ой строки и j-го столбца равно расстоянию между i-ой и j-ой вершинами. Если такого ребра нет то значение равно Infinity – просто большому числу (машинная бесконечность);

Color – массив цветов вершин;

Ribs – в этом массиве запоминаются найденные ребра;

a, b – вершины, соединяемые очередным минимальным ребром

len – длина дерева.

Матрицу расстояний будем хранить в текстовом файле INPUT.MTR, где число на первой строке – количество вершин n, а остальные n строк по n чисел в каждой – матрица расстояний. Если расстояние равно 1000 (Infinity), то такого ребра нет.

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;