Поиск в ширину в графе Опции

[Aleks]

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

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

[Aleks]

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

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

Исходный код

const
maxraz=400;
type index=^list;
list= record
inf: word;
next: index;
end;
connection=array[1..maxraz] of index;
var
lst,m: connection;
.....

***Процедура создания графа в динамической памяти***}
procedure Make_Graph(mgsi: boolean);
label Er;
var
n: index;
i,j: word;
kolvo: longint;
spro: boolean;
begin
randomize;
for i:=1 to raz do begin
ver[i]:=random(1000);
end;
kolvo:=0;
for i:=1 to raz do begin
lst[i]:=nil;
for j:=1 to raz do begin
spro:=true;
if j=raz then goto Er;
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
begin
new(m[i]); inc(kolvo);
m[i]^.inf:=ver[j];
m[i]^.next:=lst[i];
lst[i]:=m[i];
end;
Er:
end;
end;
writeln;
if mgsi then {ВЫВОД СВЯЗЕЙ ВЕРШИН}
for i:=1 to raz do {}
begin {}
write(ver[i],' '); {}
m[i]:=lst[i]; {}
if m[i]<>nil then {}
repeat {}
write(m[i]^.inf,'═'); {}
m[i]:=m[i]^.next; {}
until m[i]=nil; {}
writeln(' '); writeln; {}
end; {}
writeln('КОЛ-ВО РЕБЕР СОЗДАННОГО ГРАФА: ',kolvo);
end;
........

Сообщение отредактировано: volvo - 15.09.2005 11:14