Помогите решить задачу
Напишите и используйте в программе процедуру поиска в ширину в графе, заданном списками инцидентности. Выведите на экран номера всех вершин в порядке очередности просмотра.

я не знаю с чего начать, посмотрел в "FAQ" но не смог разобраться

Вот тут глянь: http://alex.fanshop.ru/articles/graphs.shtml

я написал код для создания графа
в реезультате...
задаем количество вершин графа – 5
ребра между ними формируются случайным образом.
Список инцидентности созданного графа:
269-> 327-§
679-> 327-12-§
12-> 327-269-§
327-> 525-§
525-> 12-269-§
КОЛ-ВО РЕБЕР СОЗДАННОГО ГРАФА: 8
Примечание: символ «§» соответствует концу списка (nil).

я правильно понимаю алгоритм поиска в ширину в графе (см.рисунок)
порядок очередности просмотра будет: 269, 12, 327, 525, 679

может ли быть, порядок очередности просмотра графа: 269, 525, 327, 12, 679 (см.рис выше)


Подскажите, пожалуйста, а то у меня все застопорилось, не могу определиться в алгоритме просмотра графа в ширину

Вот принцип поиска в ширину:

По-моему, порядок обхода "269, 525, 327, 12, 679" не противоречит этому принципу...

volvo спасибо за ссылку. Программа работает.

не мог бы ты мне объяснить назначение переменной lst, m (это код из твоей ссылке http://alex.fanshop.ru/articles/graphs.shtml), а то я переделал немного код (но не совсем понимаю их назначение: m[i] –> содержит для каждой вершины в памяти данные)
и еще вопрос как освободить память, не могу сообразить

Расшифровка - дальше в тексте программы:

{указатель на начало списка связей v-й вершины}
m[v]:=lst[v];

, откуда становится ясно, что lst[ i ] содержит список связей вершины i

как освободить память, не могу сообразить

А что, Mark/Release уже отменили? ;)

Var
  p_start: Pointer;
...
WriteLn(MemAvail);
Mark(p_start); { перед созданием графа }
... { работа с графом }
Release(p_start); { вернемся к состоянию, которое было до Mark }
WriteLn(MemAvail);
...

Спасибо volvo, что бы я делал без тебя

volvo не затруднит тебя дать заключение по этой проге
где есть огрехи, которые следовало бы исправить.

Заранее благодарю за помощь.

:D Делал бы сам ...


Огрех или не огрех, но такие вещи не приветствуются, потому что могут привести к нежелательным результатам (процедура DP_Graph)...

for j:=1 to raz do begin
  spro:= true;
  if j<> raz then begin
    if j=i then inc(j); { <--- Изменение параметра цикла в самом цикле }
    n:= nil; n:= lst[j];
    if lst[j]<>nil then
    repeat
      if n^.inf=ver[i] then spro:= false; n:= n^.next;
    until (n=nil) or (not(spro));
    if (round(random)=1) and spro then add;
  end;
end;

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

Как организовать освобождение памяти не с помощью процедур Mark и Release, а последовательным удалением элементов динамической структуры с последующим освобождением памяти с помощью процедуры Dispose.

я попробовал сам, но некоторые элементы все равно остаются в памяти

procedure  delet;
var
  h: integer;
begin
  for h:=1 to raz do
  begin
    m[h]:=lst[h];
    while m[h]<> nil do
    begin
      dispose(m[h]);
      m[h]:= nil;
    end;
  end;
end;

Вначале созавай динамические переменные с помощью New, а только потом уничтожай с помощью Dispose

Aleks, у тебя же создаются элементы m[]? Так почему бы не попробовать:

procedure  delet;
var
  h: integer;
begin
  for h:=1 to max do
    if m[h] <> nil then dispose(m[h]);
end;

? А вот lst[] тут ни при чем, а ведь удалять ты пытался именно их !!!

Результат работы программы остается 64 б
--526432
Kol-vo vershin Grapha (ne menee 4 i ne bolee 100) : 5
Kol-vo reber Grapha: 8

768->172=475=§
475->172=§
409->475=§
172->201=409=§
201->475=768=§

Vvedite iskom vershinu: 2
Vershini 2 net...
Nomera vershin v poryadke prosmotra Grapha
768 - 172 - 475 - 201 - 409 -

--526368

А ты проходил по программе в пошаговом режиме? У тебя же некоторые значения m[i] перезаписываются новыми, при этом старые, естественно, безнадежно теряются... Попробуй прогони вот такую процедуру Add:

procedure add;
begin
  WriteLn('current i = ', i);

  new(m[i]);
  m[i]^.inf:= ver[j];
  m[i]^.next:= lst[i];
  lst[i]:= m[i];
  inc(kolvo);
end;

Как только увидишь повторяющиеся значения - потерял SizeOf(list) байт...

может я ошибаюсь, но для m[i] вершины указываются связи с другими вершинами (ребра)

768->172=475=§
475->172=§
409->475=§
172->201=409=§
201->475=768=§

т.е. и получается, что 1 вершина (768) соединяется с 172 и 475
и для 1 вершины создается 2 элемента в памяти

Угу... Только вот компилятор тебя не понял, и удаляет первую вершину... А ты должен ему объяснить, что этого делать не надо, и что надо связать новую вершину с предыдущей...

а как процедура выводит связи с другими вершинами? откуда она их берет?

О !!! Меня посетила простая до невозможности идея Берешь процедуру Print_Ver, только вместо распечатки всех вершин производишь их удаление !!!

procedure delet;
var
  i: integer;
  T: index;
begin
  for i:=1 to raz do begin
    m[i]:= lst[i];
    if m[i]<>nil then
      repeat
        T := m[i];
        m[i]:= m[i]^.next;
        Dispose(T);
      until m[i]= nil;
  end;
end;

Попробуй... По-моему, должно сработать...

работает
благодарю за помощь

Amoxicillin Horse

Cialis 2.5mg Price

cialis levetra

Viagra Online Bestellen Ausland