Цикличность графа

Вопросы программирования на Free Pascal, использования компилятора и утилит.

Модератор: Модераторы

Цикличность графа

Сообщение krupstor » 29.05.2012 00:16:28

Написал программу которая проверяет на цикличнось, ацикличность граф. Свиду она работает. Например если ввести 5 и 5 т.е 5 вершин и 5 ребер и начать их вводить например 1 2,2 3,3,4,4,5,5,1 то все будет нормально и он выведет верный ответ, но если цикл в графе чуть сместит например он будет замыкаться в вершине 2. т.е 1 2,2 3,3,4,4,5,5,2 то выведет ошибку:Слишком много вызовов подпрограмм. Как исправить мою программу так, что бы не было этой ошибки и он опредилял, что граф все таки имеет цикл при таком вводе вершин.
uses crt;
var
a: array [1..100,1..100] of integer;
n,m,x,y,i,j,b: integer;
procedure rec(v: integer);
var
k: integer;
begin
for k:=1 to n do
if a[v,k]=1 then
if k=i then b:=1- предпологаю что тут как то нужно исправть, но всю голову уже сломал и не пойму как. :cry:
else rec(k);
end;
begin
writeln('Vvedite vershini i rebra');
readln(n, m);
for i:=1 to n do
for j:=1 to n do
a[i,j]:=0;
for i:=1 to m do
begin
write('Koordinati ',i,' rebra- ');
readln(x,y);
a[x,y]:=1;
end;
b:=2;
for i:=1 to n do
rec(i);
if b=1 then
writeln('Graph imeet cikl')
else
writeln('Graph ne imeet cicla');
readln;
end.
krupstor
незнакомец
 
Сообщения: 2
Зарегистрирован: 29.05.2012 00:06:25

Re: Цикличность графа

Сообщение tema » 29.05.2012 03:27:44

Помню давным давно в институте досталась мне именно эта задача.
Алгоритм, который пытаешься реализовать в студию.
tema
постоялец
 
Сообщения: 376
Зарегистрирован: 24.03.2011 20:19:27

Re: Цикличность графа

Сообщение Ask » 29.05.2012 11:12:56

if visited[k] then begin b:=1; exit; end else visited[k] := true;
Ask
постоялец
 
Сообщения: 163
Зарегистрирован: 25.12.2008 03:51:37

Re: Цикличность графа

Сообщение krupstor » 29.05.2012 19:08:38

мм а что такое visited?
krupstor
незнакомец
 
Сообщения: 2
Зарегистрирован: 29.05.2012 00:06:25

Re: Цикличность графа

Сообщение Ask » 30.05.2012 01:30:52

Предлагаю тщательно подумать и догадаться.
Если не получится, значит основы алгоритмов изучать ещё рано,
нужно повторить основы ЯП Паскаль.

Кстати, else в начале следующей строки тоже нужно убрать.
Ask
постоялец
 
Сообщения: 163
Зарегистрирован: 25.12.2008 03:51:37


Вернуться в Free Pascal Compiler

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3

Рейтинг@Mail.ru