Графы Опции

[Юлия92]

1)Добрый день люди есть псевдокод методичка Земленухина по которому не все понимаю.Непонятны в описании на паскаль..7 и 10 строки...помогите кто чем может)))

1.	for iX do num[i]:=0; ftr[i]:=0
2.	for i=1 to m do numBL[i]:=0
3.	k:=1; kU:=0;  SU:=nil; cntBL:=0; U:=nil;
4.	for rX 
5.	         do    if  num[r]=0  
6.	                                then   BLOCK(r)

BLOCK(i)
1.	num[i]:=k; L[i]:=k k:=k+1
2.	for   jГ[i]  
3.	         do    if  num[j]=0  
4.	                         then  SU (i,j)
5.	                                  ftr[j]:=i
6.	                                  BLOCK(j)
7.	                                  L[i]:=min(L[i],L[j])
8.	                                  if L[j]  num[i]  
9.	                                             then cntBL:=cntBL+1
10.	                                                      while Top(SU)  (i,j) 
11.	                                                                     do u  SU ; U  u                                                                                                                                        
12.	                                                                           kU:=kU+1
13.	                                                                           numBL[kU]:=cntBL
14.	                          else   if  j  ftr[i]
15.	                                               then  SU (i,j)
16.	                                                         L[i]:=min(L[i],num[j])

2)Применение Пвш...Надо найти экцентриситет (максимальный num) радиус(min num)диаметр(максимальный экцетриситет),а как найти матрицу расстояний и диаметральную цепь??? и как это все всунуть в пвш???

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

Землячка,
- в 7 строке функция min, я не думаю что это проблема;
- в 10 строке самописная функция Top(SU) - значение объекта с вершины стека SU.

В процедурах используются два стека SU и u. Покажи как ты их реализовала (структура, Push, Pop) и на основании этого можно реализовывать Top. Кстати, обрати внимание, что в стек помещаются объекты - дуги графа - характеризуемые двумя числами (начало и конец).
Также в строке 10 нужно реализовать сравнение этих дуг - это лучше реализовать отдельной функцией.

В общем, всё упирается в твою реализацию. Приводи код.

P.S. Поищи эту методичку в сети - в электронном виде исправлены некоторые неточности и ошибки. В частности в строке 14 условие несколько сложнее. И ещё, просто из любопытства - методичка Земленухина или Землянухиной?

По второму вопросу мне нечего сказать.

[Юлия92]

Землячка?)))методичка Землянухины(авторы мужчина и женщина)))).А на лекции нам вообще давали другой малец код,(там вообще нет функцииTOP)Вот то на что меня хватило по реализациии(((...как обычно не густо....но очень очень надо сделать эту лабу (((сижу и мучаюсь

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

var
  i,j,r,k,cntBL: integer;
  num, ftr,L,Su      : TArray;
  Matrix : TMatrix; 
  n    : integer; 

function min(a,b:integer):integer;
begin
if a>b then min:=b
else
min:=a;
end;

procedure Blok(r:integer);
var
  j:integer;

begin
  num[r]:=k;
  L[r]:=k;
  k:=k+1;

  for j:=1 to n do
  begin
    if (Matrix[r, j]<>0) and (num[j]=0) then
    begin
      Su[k]:=Matrix[r,j];
      ftr[j]:=r;
      Blok(j);
    end;
  end;
  L[r]:=min(L[r],L[j]);
                       if L[j]>=num[r] then
                        begin
                       cntBl:=cntBl+1
                       end
                       else
                        if j<>ftr[r] then
                       L[r]:=min(L[i],num[j])
end;

begin
  clrscr;

  writeln('----Mosti,Bloki,tochki razdela-----');

  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;

  writeln('Матрица смежности');
  for i:=1 to n do
  begin
    for j:=1 to n do
      write(Matrix[i,j],' ');
    writeln;
  end;
  writeln;


  writeln('Результат :');
  for i:=1 to n do
  begin
    num[i]:=0; {ни одна вершина не посещалась}
    ftr[i]:=0;
     end;
    k:=1;
    cntBl:=0;
    {U:=0;}


  for r:=1 to n do
    if num[r]=0 then Blok( r );

  


  writeln;
  readln;
end.

Сообщение отредактировано: Юлия92 - 28.05.2012 22:32

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

Пообещай не строить самолёты и атомные станции !!!!!!!

Удивительно, но несмотря на название алгоритма в методичке, он не даёт в ответе именно мосты и точки раздела, а только блоки.

Мосты можно получить при проверке в BLOCK условия (L[j]>num[r]) {добавленная строка 7.1}.

Точки раздела получаются ниже при проверке (L[j]>=num[r]) {строка 8}. Но это действительно для всех вершин кроме корневой. В методичке что-то об этом есть.

Можешь "малец" почитать по теме на "http://e-maxx.ru/algo/" или погуглив.

По-хорошему, работу со стеком и со списком нужно вынести во внешний модуль - вспомогательные процедуры занимают слишком много места в тексте.

И ещё раз - не проектировать никаких подводных лодок, никаких самолётов... Ничего...

[Юлия92]

Паш спасибо огромное....только почему то ошибка и в одном и другом файле в строке объявления function StackTop...34 (invalid function result type),т.е не верный тип возвращаемого значения функции и так во всех функциях(((((( так что даже если захочу построить самолеты не получится

Сообщение отредактировано: Юлия92 - 29.05.2012 22:22

[IUnknown]

только почему то ошибка и в одном и другом файле в строке объявления function StackTop...34 (invalid function result type),т.е не верный тип возвращаемого значения функции

Турбо-Паскаль что-ли используешь? Тогда да, там нельзя возвращать из функции ничего кроме встроенных типов данных. Никаких структур. Придется переделывать функции на процедуры:

procedure StackTop(const Stack : TStackEdge; var Res : TEdge);
begin
  Res:=Stack.Storage[Stack.Depth];
end;

, и все в таком духе. Ну, и вызовы функций, разумеется, переделывать... matrix.pas я приложил (компилируется, на работоспособность не проверял), второй файл - по аналогии измени.

Сообщение отредактировано: IUnknown - 29.05.2012 22:40

[Юлия92]

Спасибо за помощь все понятно)))разобралась

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

И хорошо!

В какой-то предыдущей теме с графами в коде были комментарии "//" - в стиле Delphi/FPC. Отсюда и моя уверенность в допустимости такой конструкции.