Program prim;
function findMinKey(key: array of integer; mstSet: array of boolean): integer;
var min, min_index, n: integer;
begin
n := length(key);
min := MaxInt;
for var v := 0 to (n - 1) do begin
if (mstSet[v] = false) and (key[v] < min) then begin
min := key[v];
min_index := v;
end;
end;
findMinKey := min_index;
end;
procedure printMST(parent: array of integer; graph: array of array of integer);
var mst, n: integer;
begin
n := length(parent);
writeln('Дерево -> Вес');
for var i := 1 to (n - 1) do begin
writeln(parent[i], ' - ', i, ' -> ', graph[i][parent[i]]);
mst := mst + graph[i][parent[i]];
end;
writeln('МОД:', mst);
end;
// Minimum Spanning Tree
procedure findMST(graph: array of array of integer);
var parent, key: array of integer;
mstSet: array of boolean;
u, n: integer;
begin
n := length(graph);
setLength(parent, n);
setLength(key, n);
setLength(mstSet, n);
for var i := 0 to (n - 1) do begin
key[i] := MaxInt;
mstSet[i] := false;
end;
key[0] := 0;
parent[0] := -1;
for var count := 0 to (n - 2) do begin
u := findMinKey(key, mstSet);
mstSet[u] := true;
for var v := 0 to (n - 1) do begin
if (graph[u][v] > 0) and (mstSet[v] = false) and (graph[u][v] < key[v]) then begin
parent[v] := u;
key[v] := graph[u][v];
end;
end;
end;
printMST(parent, graph);
end;
procedure fillFromFile(path: string; var arr: array of array of integer);
var F: TextFile;
n: integer;
begin
assignfile(F, path);
reset(F);
while not eof(F) do begin
readlnstring(F);
inc(n);
end;
closefile(F);
SetLength(arr, n);
for var i := 0 to (n - 1) do begin
SetLength(arr[i], n);
end;
assignfile(F, path);
reset(F);
for var j := 0 to n - 1 do begin
for var i := 0 to n - 1 do begin
read(F, arr[i][j]);
end;
end;
closefile(F);
end;
procedure fillRandom(var arr: array of array of integer);
var n: integer;
begin
n := random(2, 5);
SetLength(arr, n);
for var i := 0 to (n - 1) do begin
SetLength(arr[i], n);
end;
for var j := 0 to n - 1 do begin
for var i := 0 to n - 1 do begin
arr[i][j] := random(0, 5);
end;
end;
end;
procedure writeArray(var arr: array of array of integer);
var n: integer;
begin
n := length(arr);
for var i := 0 to (n - 1) do begin
for var j := 0 to (n - 1) do begin
if(j = 0) then begin
write('|');
end;
write(arr[i, j]);
if(j = (n - 1)) then begin
write('|');
end;
if(length(arr[i, j].toString) > 1) then begin
write(' ');
end else begin
write(' ');
end;
end;
writeln;
end;
end;
var matrix: array of array of integer;
n, switch: integer;
filename: string;
begin
writeln('1 - ввод из файла, 2 - случайные числа, 3 - ручной ввод');
read(switch);
case switch of
1: begin
fillFromFile('6.txt', matrix);
end;
2: begin
read(filename);
writeln(filename);
fillRandom(matrix);
end;
else begin
writeln('Введите размерность матрицы:');
read(n);
SetLength(matrix, n);
for var i := 0 to (n - 1) do begin
SetLength(matrix[i], n);
end;
for var j := 0 to n - 1 do begin
for var i := 0 to n - 1 do begin
read(matrix[i][j]);
end;
end;
end;
end;
writeln('Введенная матрица:');
writeArray(matrix);
findMST(matrix);
end.