Графы. Фундаментальная система циклов связного графа Опции

[Юлия92]

Написала программу по псевдокоду...Но результат работы процедур не выдается....Не пойму в чем проблема...Пседокод прилагаю..заранее благодарю за помощь))

uses crt;
const
  max=50;
type
    TMatrix = array [1..max,1..max] of byte;
    TArray  = array [1..max] of integer;

var
    i,j,m,k,z : integer;
    num,ftr,masQ: TArray;
    Matrix : TMatrix; {матрица смежности}
    n ,nz: integer; {количество вершин графа}

procedure save(i,j,nz:integer);
begin
     z:=i;
        while z<>j do
                begin
                     masQ[nz]:=z;
                     z:=ftr[z];
                     masQ[nz]:=j;
                     masq[nz]:=i;
                end;
end;
procedure cicle(i:integer);
var
  j:integer;

begin
     k:=k+1;
     num[i]:=k;
  for j:=1 to n do
  begin
    if (Matrix[i, j]<>0) and (num[j]=0) then
       begin
            ftr[j]:=i;
            cicle(j);
       end
          else if ftr[i]<>j then
               begin
                    nz:=nz+1;
                    save(i,j,nz);
               end;
end;
end;

begin
  clrscr;

  writeln('=======Фундаментальная система циклов связного графа====');

  write('Введите количество вершин графа:');
  readln(n);
  writeln('Заполнение матрицы смежности');
  for i:=1 to n do
    for j:=1 to n do
    begin
      Write('(',i,',',j,')=');
      read(Matrix[i,j]);
      if Matrix[i,j] <> 0 then Matrix[i,j]:=1;
    end;
{$endif}
  //вывод матрицы смежностиж;
  writeln('Матрица смежности');
  for i:=1 to n do
  begin
    for j:=1 to n do
      write(Matrix[i,j],' ');
    writeln;
  end;
  writeln;


  writeln('Результат :');
  n:=0; m:=0;
  for i:=1 to n do
  begin
    num[i]:=0; {ни одна вершина не посещалась}
    ftr[i]:=0;
    n:=n+1;
    m:=m+(n*n);
    m:= round(m / 2);
    k:=1;
  end;
  for i:=1 to m-n+1 do
  begin
  masQ[i]:=0;
  k:=0;
  nz:=0;
  cicle(i);

  //вывод массивов  num ftr;
  write('num: ');
  for i:=1 to n do
    write(num[i]:3);
  writeln;
  write('ftr: ');
  for i:=1 to n do
    write(ftr[i]:3);
  writeln;
  write('masQ:  ');
  for i:=1 to n do
    write(masQ[i]:3);
  writeln;
  write('nz:  ');
    write(nz);
  writeln;
  readln;
end;
end.
 

[Федосеев Павел]

Юль, ты делаешь все механически, не вникая.
Мне проще отдать тебе готовый код, чем объяснять.

В архиве две папки. В одной работающий код по псевдокоду, с учётом примечания, найденного в книге Окулова о том, что к сохранению цикла переходим не только когда j вершина не предыдущая для i, но и когда при построении дерева поиска в глубину i вершина встретилась после j (т.е. найдено обратное ребро - ведущее вверх).

Поиск в глубину является естественным подходом, используемым для нахождения фундаментальных циклов. Строится каркас, а каждое обратное ребро порождает цикл относительно этого каркаса. Для вывода циклов необходимо хранить порядок обхода графа при поиске в глубину (номера вершин) — массив St, а для определения обратных ребер вершины следует «метить» (массив Gnum) в той очередности, в которой они просматриваются. Если для ребра <v,j> оказывается, что значение метки вершины с номером j меньше, чем значение метки вершины с номером i, то ребро обратное и найден цикл.

Во второй папке программа с аналогичной функциональностью, встретившаяся мне на одном из форумов. Топикстартер утверждал, что она из книги Иванов Б.Н. "Дискретная математика. Алгоритмы и программы." Она мне просто понравилась.

В обоих случаях я использовал пример из твоей методички. Кстати, в интернете она встречается в pdf и с внесёнными исправленями.

Сообщение отредактировано: Федосеев Павел - 16.05.2012 23:53