Консультация № 198343
23.04.2020, 12:13
0.00 руб.
30.04.2020, 18:03
0 1 0
Здравствуйте, уважаемые эксперты! У меня возникла проблема, я не знаю как реализовать минимальное островное дерево, в моей программе осталось только выбрать рёбра, чтобы цикл был не замкнут. Можете пожалуйста помочь, или может быть идею подсказать, как это организовать? (среда PascalABC.NET)
[code lang=pascal]Program Graphs;
Program Graphs;
const
n = 6;

type
Matrix = array[1..n, 1..n] of integer;
Boollist = array [1..n] of boolean;
Intlist = array [1..n] of integer;
mat1=array[1..20,1..20] of integer;

var
sup_mat,KR1: matrix;
KR2:array [1..n*n,1..n*n] of integer;
KR3:array [1..n*n] of integer;
KR4:array [1..n*n] of integer;
sup_int: intlist;
visit: boollist;
res: string[100];
s, sum: integer;
min,z:integer;
Graf1,Graf2: array [1..20] of integer;

procedure OpenFile(var my_m: matrix);//открывает файл и читает из него массив
var
t: text;
i, j, sup, x: integer;
begin
assign(t, 'graf.txt');
reset(t);
for i := 1 to n do
for j := 1 to n do
begin
read(t, sup);
my_m[i, j] := sup;
end;
close(t);
end;
procedure smej;
var i:integer;
begin
writeln('Матрица смежностей графа');
writeln;
write(' '); //
//textcolor(23);
for i:=1 to n do write('| ',i);
if i=n then write('|'); writeln('');
for i:=1 to n do
begin
write(i,'|');
for var l:=1 to n do
begin
if sup_mat[i,l]>=10 then write( sup_mat[i,l],'|')
else write(' ', sup_mat[i,l],'|');
end;
writeln('');
end;
end;
begin
OpenFile(sup_mat);//
smej;
KR1:=sup_mat;
var i,j,k:integer;
k:=1;
for i:=1 to n do
for j:=1 to n do begin
if KR1[i,j]<>0 then begin
if KR1[i,j]<= KR1[j,i] then begin
KR2[1,k]:=i*10+j;
KR2[2,k]:=KR1[i,j];;
KR1[j,i]:=0
end
else begin
KR2[1,k]:=j*10+i;
KR2[2,k]:=KR1[j,i];
KR1[i,j]:=0;
end;
k+=1;
end;


end;
for i:=1 to n do begin
for j:=1 to n do
write (KR1[i,j],' | ');
writeln();
end;
var b,count,k1,k2,DKR:integer;
count:=n;
DKR:=0;
for i := k-1 downto 1 do //сортировка рёбер по возрастанию веса
for j:=1 to i-1 do if KR2[2,j] > KR2[2,j + 1] then
begin
b := KR2[2,j];
KR2[2,j] := KR2[2,j+1];
KR2[2,j+1] := b;
b := KR2[1, j];
KR2[1, j] := KR2[1, j+1];
KR2[1, j+1] := b;

end;
{ for i:=1 to k-1 do begin
while (count>1) do begin
k1:=KR2[1,i]div 10;
k2:= KR2[1,i]mod 10;
DKR+=KR2[2,i];
count-=1;
if KR1[k1,k2]<>k2 then }
end.[/code]

Обсуждение

давно
Старший Модератор
31795
6196
02.05.2020, 16:53
общий
Адресаты:
Цитата: Be|_Ena
Можете пожалуйста помочь, или может быть идею подсказать, как это организовать?

Если только идею: Минимальное остовное дерево. Алгоритм Прима. Алгоритм Крускала, там есть код на С++, который можно передалать.
Об авторе:
Мне безразлично, что Вы думаете о обо мне, но я рад за Вас - Вы начали думать.

Форма ответа