VPF::Задача на графы. - Форум программистов

Joil

Дата 16.2.2008, 20:17 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 211
Регистрация: 24.1.2008

Репутация: нет
Всего: 8

Какая то адская задача smile

:
С помощью метода поиска в глубину найдите стягивающее дерево для произвольного связного неориентированного графа, заданного списками инцидентности.
--------
Люди, пожалуйста помогите. Может, если у кого есть ссылки по теме, или задачи похожие, или может примерно алгоритм решения хоть напишите.
Буду рад любой помощи.
Заранее спасибо.

Это сообщение отредактировал(а) Joil - 17.2.2008, 06:56

--------------------

Who had deceived thee so often as thyself? © Benjamin Franklin--------------------Always bear in mind that your own resolution to succeed is more important than any other. © Abraham Lincoln--------------------If you need it - do it, if you want it - take it! © ...

Wowa

Дата 17.2.2008, 12:12 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Админ
Сообщений: 15017
Регистрация: 14.9.2000
Где: Винград

Репутация: нет
Всего: 290

Сделай для начала картинку графа и загрузи её сюда, имхо. Тогда по ней будет видно, как алгоритм должен работать.

А вообще, есть же алгоритм глубинного поиска. Чем он не подходит?

Dobermann

Дата 18.2.2008, 16:00 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 992
Регистрация: 7.1.2008

Репутация: нет
Всего: 0

Код


program DearchInDepth;
const lim=10; uses crt;
type Mtr=array[1..lim,1..lim]of byte;
     lab=array[1..lim]of boolean; 
var A:Mtr; new:lab;n,i:byte; 
Rebra:array[1..2,1..lim]of byte;
cnt,tek,pred:byte;
procedure Vvod; var i,j:byte;
begin write('n=');
readln(n); for i:=1 to n do 
begin
write(i,'>');read(j); 
while j>0 do 
begin 
a[i,j]:=1; read(j)
end end end;
procedure PoiskGlub(v:byte);
var j:byte; 
begin 
new[v]:=false;
write(v:3); for j:=1 to n do if(a[v,j]>0)
and new[j] then 
begin 
PoiskGlub(j); inc(cut);
rebra[1,cnt]:=v; rebra[2,cnt]:=j 
end end;
begin 
clrscr; fillchar(new, sizeof(new),true);
fillchar(a,sizeof(a),0); vvod; cnt:=0; 
for i:=1 to n do if new[i] then PoiskGlub(i);
writeln;writeln('Rebra:'); for i:=1 to cnt do
writeln(rebra[1,i],' ',rebra[2,i]); readln
end.

Вот тебе поиск в глубину (пр.неор. граф).

Joil

Дата 20.2.2008, 07:30 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 211
Регистрация: 24.1.2008

Репутация: нет
Всего: 8

Dobermann, Very Great Thanks, незнаю что бы без тебя делал. smile

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Object Pascal: кроссплатформенные технологии \| Следующая тема »