Для организации хранения данных нам потребуется:
Program Menger;
Const maxn =15;
Type matrix = array [1..maxn,1..maxn] of integer;
Boolmas = array [1..maxn] of boolean;
mas = array [1..maxn] of integer;
var N: integer; {количество вершин в графе}
A: matrix; {матрица смежности}
Val_V: mas; {массив для запоминания валентности вершин}
Также нам потребуется логический массив В для запоминания «посещаемости вершин»: были мы в этой вершине или нет. И потребуется массив Num
для хранения и выведения вершин, входящих в <u,v>-цепь. Но их мы опишем в основной процедуре Solve.
Напишем костяк процедуры Solve:
Procedure Solve;
var B: boolmas;
Num: mas;
u,v: integer;
begin
for u:=1 to N-1 do
for v:=u+1 to N do begin
write (u,’ – ‘,v);
if A[u,v]=1 then writeln (‘ смежные ‘) {1й случай}
else if (Val_V[u]=1) or (Val_V[v]=1) then writeln (‘ 1′) {2й случай}
else begin
… {3й случай}
end;
end;
end;
Как уже было сказано, 3й случай – самый интересный. Для его реализации будем использовать модификацию рекурсивного поиска в глубину. (Подробное рассмотрение логики поиска в глубину можно найти в [2] стр. 10-11 и [3] стр. 37-40)
Procedure Search_Depth (i:integer; var k:integer);
var j:integer;
begin
Num[k]:=i;
B[i]:=True;
for j:=1 to N do
if (A[i,j]=1) and (B[j]=false)
then begin
inc(k);
Search_Depth(j,k);
end;
end;
При написании программы следует учесть некоторые особенности:
· Во-первых, сам способ выведения <u,v>-цепей на экран. Для запоминания цепей мы должны формировать массив Num заново.
Решение: каждый раз как мы выходим из рекурсии, уменьшаем k (индекс вершины в <u,v>-цепи)
Loading ...