while notRow_IsVisited(Visited) do

for var i:=1 to N do if not Visited[i] then DepthSearch(i);

delete(Path, 1, 2);

writeln('Путь обхода: ', Path);

end;

 

function minf(x, y: integer): integer;

Begin

if x > y then minf:=y else minf:=x;

end;

 

//определить кратчайший путь из заданной вершины во все остальные

procedure Path_Short(g: TAdMatrix; x: byte);

Const

max = 1000000;

Var

d, s, p: TIList;

min, z, k: integer;

Begin

write('Введите вершину для нахождения кратчайшего пути от нее ко всем остальным: ');

readln(x);

min:=1000;

z:=1;

for var i:=1 to n do

for var j:=1 to n do

if (i <> j) and (g[i, j] = 0) then g[i,j]:=max;

for var i:=1 to n do

Begin

s[i]:=0;

d[i]:=g[x,i];

p[i]:=1;

end;

s[x]:=1;

p[x]:=0;

for var i:=1 to n do

Begin

for var j:=1 to n do

if (d[j] < min) and (d[j] <> 0) and (s[j] = 0) then

Begin

min:=d[j];

z:=j;

end;

s[z]:=1;

for k:= 1 to n do

if s[k]=0 then

Begin

d[k]:=minf(d[k], d[z] + g[z,k]);

p[k]:=k;

end;

min:=1000;

end;

for var i:=1 to n do write(i:2,' ');

write(' - Вершины графа');

writeln();

for var i:=1 to n do write(d[i]:2,' ');

write('- Кратчайшие расстояния');

writeln;

end;

 

//построение минимального остовного дерева

procedure OstovTree_Prim(g: TAdMatrix; var u: TIList);

Var

i,j,z,min,mi,mj,f,f2,tmp: byte;

vu, u1: TIList;

Begin

write('Введите вершину с которой следует начать построение: ');

readln(z);

min:=100;

f:=0;

f2:=0;

for i:=1 to n do

Begin

vu[i]:=1;

u[i]:=0;

u1[i]:=0;

end;

u[z]:=1;

u1[z]:=1;

vu[z]:=0;

i:=1;

z:=2;

while z <= n - f2 do

Begin

for i:=1 to n - f2 do if u1[i] = 1 then

for j:=1 to n - f2 do if (g[i, j] < min) and (g[i, j] > 0) and (u1[j] = 0) then

Begin

min:=g[i,j];

mi:=i;

mj:=j;

end;

u[mj]:=z;

u1[mj]:=1;

g[mi, mj]:=0;

g[mj, mi]:=0;

inc(z,1);

min:=100;

end;

for i:=1 to n do write(i:2,' ');

writeln(' - Вершины графа');

for i:=1 to n do

Begin

write(u[i]:2, ' ');

tmp:=tmp + u[i];

end;

writeln(' - Порядок их добавления в остовное дерево');

write('Суммарный вес - ',tmp);

writeln('');

end;

 

//вывод меню

procedure Menu;

Var

MI, a: integer;

Begin

writeln('');

writeln('=========================================================');

writeln('Выберите действие: ');

writeln('1. Загрузить граф из файла.');

writeln('2. Определение самого короткого цикла в графе.');

writeln('3. Выполнить обход графа в глубину.');

writeln('4. Определить кратчайший путь из заданной вершины во все остальные.');

writeln('5. Построить минимальное остовное дерево с помощью алгоритма Прима.');

writeln('6. Выход из программы.');

write('Введите номер действия: ');

readln(MI);

CaseMI of

1: begin write('Введите номер графа: '); readln(a); OpenFile(a, Gr); writeln('Граф загружен!'); Menu; end;

2: begin Find_ShortLoop(Gr); Menu; end; //Нахождение короткого цикла

3: begin write('Введите номер вершины, с которой необходимо начать обход: '); readln(a); Share_Deep(Gr, a); Menu; end; //Обход графа в глубину

4: begin Path_Short(Gr, 1); Menu; end; //Определение кратчайшего пути из заданной вершины во все остальные

5: begin OstovTree_Prim(Gr, Mot); Menu; end; //Построение минимального остовного дерева

6: exit;

end;

end;

 

Begin

//загружаем файл

OpenFile(0, Gr);

//отображаем меню

Menu;

end.