Program prim название программы можно изменить на любое function findM

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
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. // конец программы