Program prim; // название программы, можно изменить на любое
function findMinKey(key: array of integer; mstSet: array of boolean): integer;
{
Функция поиска минимального ключа в массиве key
Входные значения:
key (array of integer) - одномерный динамический массив целочисленных значений, содержащий значений ключей всех вершин.
mstSet (array of boolean) - одномерный динамический массив булевых значений (true или false) содержащий вершины, уже включенные в MST (Minimum Spanning Tree - Минимальное остовное дерево)
Выходное значение:
min_index с типом данных integer (целочисленное значение)
}
var min, min_index, n: integer;
{
Идентификаторы функции findMinKey:
min (integer(целочисленное значение)) - минимальное значение
min_index (integer(целочисленное значение)) - индекс минимального значения
n (integer(целочисленное значение)) - размерность массивов key и mstSet
}
begin // начало функции findMinKey
n := length(key); // получаем размерность переданного в функцию массива key и присваиваем его в переменную n
min := maxInt; // присваиваем переменной min значение maxInt (2147483647)
for var i := 0 to (n - 1) do begin // цикл от 0 до (n - 1)
if (mstSet[i] = false) and (key[i] < min) then begin
{
условие, если mstSet(описание выше) с индексом i ложь (false)
and (и) key с индексом i меньше min - тогда:
}
min := key[i]; // присваиваем переменной min значение из массива key с индексом i
min_index := i; // присваиваем переменной min_index значение i (индекс массива key с минимальным элементом)
end; // конец условия if
end; // конец цикла for
findMinKey := min_index; // в Pascal так описывается return. (Функция вернет значение min_index)
end; // конец функции findMinKey
function printMST(parent: array of integer; graph: array of array of integer): string;
{
Функция вывода результата выполнения алгоритма
Входные значения:
key - одномерный динамический массив, содержащий ключи хранящиеся в setMST
mstSet - массив вершин, уже включенных в MST (Minimum Spanning Tree - Минимальное остовное дерево)
n - размерность массивов key и mstSet
Выходное значение:
min_index с типом данных integer (целочисленное значение)
}
var mst, n: integer;
return: string;
{
Идентификаторы функции printMST:
mst (integer) - значение MST(МОД) - длина Минимального Остовного Дерева
n (integer) - размерность массивов key и parent
return (string) - переменная для вывода в консоль, а также записи в файл резульата поиска МОД, хранит значение вида:
Дерево -> Вес
6 - 1 -> 5
5 - 2 -> 1
0 - 3 -> 2
МОД: 8
}
begin // начало функции writeArray
n := length(parent); // получаем размерность переданного в функцию массива parent и присваиваем его в переменную n
return := 'Дерево -> Вес' + #10; // присваиваем переменной return текстовое значение. #10 это символ переноса на следующуй строку, как /n в других ЯП.
for var i := 1 to (n - 1) do begin // цикл от 1 до n - 1
return += parent[i] + ' - ' + i + ' -> ' + graph[i][parent[i]] + #10;
{
добавляем к переменной return -
parent[i] - значение из массива с индексом i
i - текущая итерация цикла
graph[i][parent[i]] - значение из массива graph с индексом i и индексом parent[i].
#10 символ переноса на следующуй строку
результат выполнения, для примера: 5 - 2 -> 1
}
mst := mst + graph[i][parent[i]]; // на каждой итерации прибавляем к mst значение graph[i][parent[i]].
end; // конец цикла
return += 'МОД: ' + mst; // добавляем к переменной return текст в конце (МОД: 16, например)
printMST := return; // в Pascal так описывается return. (Функция вернет значение return)
end; // конец функции printMST
// Minimum Spanning Tree
function findMST(graph: array of array of integer): string;
{
Функция поиска минимального остовного дерева (MST(Minimum Spanning Tree) или МОД на русском) (Алгоритм Прима)
Входные значения:
graph - двумерный динамический массив, который представляет собой матрицу смежности, которая задается пользователем/случайно в основном теле программы
результат выполнения функции printMST(parent, graph) с типом данных string (строка, которая после выведется в консоль и сохранится в файл, при необходимости)
}
var parent, key: array of integer;
mstSet: array of boolean;
u, n: integer;
{
Идентификаторы функции findMST:
parent (array of integer) - одномерный динамический массив целочисленных значений. Используется для хранения индексов родительских узлов в MST(минимальном остовном дереве),
а также для отображения построенного MST.
key (array of integer) - одномерный динамический массив целочисленных значений. Используется для хранения значений ключей всех вершин
mstSet (array of boolean) - одномерный динамический массив булевых значений (true или false) содержащий вершины, уже включенные в MST (Minimum Spanning Tree - Минимальное остовное дерево)
u (integer) - вершина
n (integer) - размерность массивов key и parent
}
begin // начало функции writeArray
n := length(graph);
{
получаем размерность переданного в функцию массива graph и присваиваем его в переменную n
т.к. матрица смежности является квадратной, то нет необходимости получать размерность массивов второго порядка
}
setLength(parent, n); // выделяем память для массива parent с размерностью n
setLength(key, n); // выделяем память для массива key с размерностью n
setLength(mstSet, n); // выделяем память для массива mstSet с размерностью n
for var i := 0 to (n - 1) do begin // цикл от 0 до (n - 1)
//Заполняем массив key значением maxInt(2147483647), а массив mstSet значением false
key[i] := maxInt; // присваиваем key[i] значение maxInt(2147483647)
mstSet[i] := false; // присваиваем mstSet[i] значение false (ложь)
end; // конец цикла
key[0] := 0; // присваиваем первому значению в массиве key - значение 0 (В яп индексы массивов начинаются с 0, поэтому это первое значение)
parent[0] := -1; // при первому значению в массиве parent значение -1
for var count := 0 to (n - 2) do begin // цикл от 0 до n - 2
u := findMinKey(key, mstSet); // присваиваем переменной u (вершине) результат выполнения функции findMinKey(key, mstSet), то есть минимальный ключ
mstSet[u] := true; // устанавливаем этой вершине значение true в массиве mstSet
for var v := 0 to (n - 1) do begin // цикл от 0 до n - 1
if (graph[u][v] > 0) and (mstSet[v] = false) and (graph[u][v] < key[v]) then begin
{
условие если graph[u][v] > 0 И mstSet[v] = false и graph[u][v] < key[v]
то есть, если значение из матрицы смежности с индексами u и v не равно нулю (то есть есть связь между вершинами)
и значение массива mstSet для вершины v равно false (ложь)
и значение из матрицы смежности с индексами u и v меньше значения из массива key для вершины v
тогда:
}
parent[v] := u; // присваиваем переменной parent[v] значение u
key[v] := graph[u][v]; // присваиваем переменной key[v] значение graph[u][v]
end; // конец условия if
end; // конец цикла for
end; // конец цикла for
findMST := printMST(parent, graph); // в Pascal так описывается return. (Функция вернет результат выполнения функции printMST(parent, graph))
end; // конец функции writeArray
procedure writeArray(var arr: array of array of integer);
{
Процедура "красивого" вывода двумерного массива в консоль
Входные значения:
arr (array of array of integer) - двумерный динамический массив целочисленных значений. Изначально пустой, будет хранить матрицу смежности из файла.
}
var n: integer;
{
Идентификаторы функции writeArray:
n (array of integer) - переменная, которая будет хранить размерность массива полученную из файла
}
begin // начало процедуры writeArray
n := length(arr); // получаем размерность массива arr и присваиваем его переменной n
for var i := 0 to (n - 1) do begin // цикл от 0 до n - 1
for var j := 0 to (n - 1) do begin // цикл от 0 до n - 1
if(j = 0) then begin // условие, если j = 0
write('|'); // то выводим палочку в начале
end; // конец условия if
write(arr[i, j]); // выводим значение arr[i, j]
if(j = (n - 1)) then begin // условие, если j = (n - 1)
write('|'); // то выводим палочку в конце
end; // конец условия if
if(length(arr[i, j].toString) > 1) then begin // условие, если размер элемента массива > 1
write(' '); // то выводим два пробела
end else begin // в противном случае
write(' '); // выводим три пробела
end; // конец условия if
end; // конец цикла if
writeln; // оператор переноса строки
end; // конец цикла if
end; // конец процедуры writeArray
procedure fillRandom(var arr: array of array of integer);
{
Процедура заполнения двумерного массива случайными числами
Входные значения:
arr (array of array of integer) - двумерный динамический массив целочисленных значений. Изначально пустой, будет хранить матрицу смежности из файла.
}
var n: integer;
{
Идентификаторы функции fillRandom:
n (array of integer) - переменная, которая будет хранить размерность массива полученную из файла
}
begin // начало процедуры fillRandom
n := random(2, 9); // присваиваем переменной n случайное значение от 2 до 9
SetLength(arr, n); // выделяем память для массива arr с размерностью n
for var i := 0 to (n - 1) do begin // цикл от 0 до n - 1
SetLength(arr[i], n); // выделяем память для массива arr[i] с размерностью n
end; // конец цикла
for var j := 0 to n - 1 do begin // цикл от 0 до n - 1
for var i := 0 to (n - 1) do begin // цикл от 0 до n - 1
arr[i][j] := random(0, 9); // присваиваем переменной arr[i][j] случайное значение от 0 до 9
arr[j][i] := arr[i][j]; // присваиваем переменной arr[j][i] значение arr[i][j] (чтобы матрица была зеркальной)
if(i = j) then begin // условие, если i = j
arr[j][i] := 0; // тогда обнуляем диагональные элементы матрицы arr
end; // конец условия if
end; // конец цикла for
end; // конец цикла for
end; // конец процедуры fillRandom
procedure fillFromKeyboard(var arr: array of array of integer);
{
Процедура заполнения двумерного массива с клавиатуры
Входные значения:
arr (array of array of integer) - двумерный динамический массив целочисленных значений. Изначально пустой, будет хранить матрицу смежности из файла.
}
var n: integer;
{
Идентификаторы функции fillFromKeyboard:
n (array of integer) - переменная, которая будет хранить размерность массива полученную из файла
}
begin // начало процедуры fillFromKeyboard
writeln('Введите размерность матрицы:'); // текст в консоль
read(n); // считываем размерность n с клавиатуры
SetLength(arr, n); // выделяем память для массива arr с размерностью n
for var i := 0 to (n - 1) do begin // цикл от 0 до n - 1
SetLength(arr[i], n); // выделяем память для массива arr[i] с размерностью n
end; // конец цикла for
for var j := 0 to n - 1 do begin // цикл от 0 до n - 1
for var i := 0 to n - 1 do begin // цикл от 0 до n - 1
read(arr[i][j]); // присваиваем переменной arr[i][j] значение с клавиатуры
end; // конец цикла for
end; // конец цикла for
end; // конец процедуры fillFromKeyboard
procedure fillFromFile(path: string; var arr: array of array of integer);
{
Процедура заполнения двумерного массива из файла
Входные значения:
path (string) - путь до файла (может принимать вид - 1.txt, тогда будет искать файл 1.txt в папке с компилированной версией программы, или c:/1.txt - абсолютный путь на ПК)
arr (array of array of integer) - двумерный динамический массив целочисленных значений. Изначально пустой, будет хранить матрицу смежности из файла.
}
var F: TextFile;
n: integer;
{
Идентификаторы функции fillFromFile:
F (TextFile) - переменная, которая будет хранить экземпляр файла.
n (array of integer) - переменная, которая будет хранить размерность массива полученную из файла
}
begin // начало процедуры fillFromFile
assignfile(F, path); // связывает дескриптор файла с бинарным или текстовым файлом
reset(F); // открывает файл F
while not eof(F) do begin // цикл пока не eof(F) (конец файла)
{Открываем файл и построчно считываем, на каждой строке инкрементируем n - получаем размерность матрицы (т.к. она квадратная, считать столбцы не нужно.)}
readlnstring(F); // построчное чтение файла
inc(n); // инкремент переменной n
end; // конец цикла while
closefile(F); // закрывает файл
SetLength(arr, n); // выделяем память для массива arr с размерностью n
for var i := 0 to (n - 1) do begin // цикл от 0 до n - 1
SetLength(arr[i], n); // выделяем память для массива arr[i] с размерностью n (т.к. это двумерный массив, то у каждого вложенного массива нужно установить размерность)
end; // конец цикла
assignfile(F, path); // связывает дескриптор файла с бинарным или текстовым файлом
reset(F);// открывает файл F
for var j := 0 to n - 1 do begin // цикл от 0 до 1 (построчное чтение)
for var i := 0 to n - 1 do begin // цикл от 0 до 1 (чтение по столбикам)
read(F, arr[i][j]); // присваиваем переменной arr[i][j] значение из файла
end; // конец цикла
end; // конец цикла
closefile(F); // закрываем файл
end; // конец процедуры fillFromFile
procedure writeInFile(path, text: string);
{
Процедура записи результата работы программы в файл
Входные значения:
path (string) - путь до файла (может принимать вид - 1.txt, тогда будет искать файл 1.txt в папке с компилированной версией программы, или c:/1.txt - абсолютный путь на ПК)
res (string) - текст, который будет записан в файл path
}
var
F: TextFile;
{
Идентификаторы функции fillFromFile:
F (TextFile) - переменная, которая будет хранить экземпляр файла.
}
begin // начало процедуры writeInFile
assign(F, path); // назначает файловой переменной имя внешнего файла
rewrite(F); // создает и открывает новый файл F
writeln(F, text); // записывает значение text в файл F
close(F); // закрывает файл F
end; // конец процедуры writeInFile
var matrix: array of array of integer;
n: integer;
switch, save: char;
filename, res: string;
{
Идентификаторы точки входа в программу:
matrix (array of array of integer) - двумерный динамический массив целочисленных значений, который будет хранить матрицу смежности
n (integer) - размерность матрицы matrix, т.к. она квадратная, достаточно размерность массива первого порядка
switch (char) - переменная, которая будет принимать значение с клавиатуры для выбора действия пользователя (1 - ввод из файла, 2 - случайные числа, 3(или любое другое значение) - ручной ввод)
save(char) переменная, которая будет принимать значение с клавиатуры для выбора действия пользователя (y - сохранить, n (или любое другое значение) - конец программы)
filename(string) - переменная, которая будет принимать значение с клавиатуры для ввода названия файла, в который пользователь захочет сохранить результат выполнения программы
res(string) - результат выполнения алгоритма в текстовом виде (findMST())
}
begin // начало точки входа (основное тело программы)
writeln('1 - ввод из файла, 2 - случайные числа, 3 - ручной ввод'); // текст в консоль
readln(switch); // считываем с клавиатуры значение переменной switch
case switch of // оператор выбора
'1': begin // если switch = 1
writeln('Введите название файла:'); // текст в консоль
readln(filename); // считываем с клавиатуры значение переменной filename
if fileExists(filename) then begin // условие, если файл существует
fillFromFile(filename, matrix); // то читаем его с помощью процедуры fillFromFile() и сохраняем результат в matrix
end else begin // в противном случае
writeln('Файл ', filename, ' не существует.'); // выдаем ошибку в консоль
exit; // принудительная остановка программы
end; // конец условия
end;
'2': begin // если switch = 2
fillRandom(matrix); // вызываем процедуру заполнения матрицы рандомными числами
end else begin // в противном случае
fillFromKeyboard(matrix); // вызываем процедуру заполнения матрицы с клавиатуры
end; // конец противного(?) случая
end; // конец оператора выбора
writeln('Введенная матрица:'); // вывод в консоль
writeArray(matrix); // вызов процедуры красивого вывода матрицы в консоль
res := findMST(matrix); // присваиваем переменной res результат работы алгоритма Прима
writeln(res); // выводим в консоль
writeln('Вы хотите сохранить результат работы программы в файл? y/n'); // выводим в консоль
readln(save); // считываем с клавиатуры значение переменной save
if(save = 'y') then begin // если save = y
writeln('Введите название файла:'); // выводим в консоль
readln(filename); // считываем с клавиатуры значение переменной filename
writeInFile(filename, res); // вызываем процедуру writeInFile, и с ее помощью сохраняем результат работы программы в файл filename
end; // конец условия
end. // конец программы