Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > DFS. Что не правильно?

Автор: FireSnake 13.2.2007, 14:25

Пишу рекурсивный обход в глубину, но он работает не правильно... не могу понять, почему выгружаясь из рекурсии он в нее не заходит более.
Входные данные
в первое строке количество вершин и количество ребер (N,E) а далее в Е строках описаны ребра соедин. вершины(граф не ориентирован)
6 6
1 2
2 4
3 4
1 3
1 5
5 6
на этом тесте вершины 5 и 6 оказываются не помеченными в ходе обхода

Код


program Poisk_v_glubinu;
const dl=100;
var a:array[1..dl,1..dl]of longint;
    b:array[1..dl]      of shortint;
    n,e,i,j:longint;

procedure ReadFile;
var v1,v2:longint;
begin
     assign(input,'in.txt');
     reset(input);

     fillchar(a,sizeof(a),0);
     fillchar(b,sizeof(b),0);

     readln(n,e);
     for i:=1 to e{!!!}do
     begin
          readln(v1,v2);
          a[v1,v2]:=1;
          a[v2,v1]:=1;
     end;

     close(input);
end;

procedure DFS(u:longint);
begin
     b[u]:=1;
     for i:=1 to n do
        if (a[u,i]=1)and(b[i]=0)then DFS(i);
end;

procedure Main;
begin
     DFS(1);
     for i:=1 to n do if b[i]=0 then break;
     if b[i]=0 then writeln('Graph not connected') else writeln('Graph connected');
end;

begin
     ReadFile;
     Main;
end.

Автор: MBo 13.2.2007, 16:22

1. счетчики циклов i сделай локальными переменными
2. проверку наличия 0 в b измени - введи булевский флаг
Flag := True;
for i:=1 to n do
  if b[i]=0 then begin
    Flag := False;
    Break;
  end;

Автор: FireSnake 13.2.2007, 20:36

Цитата

2. проверку наличия 0 в b измени - введи булевский флаг
Flag := True;
for i:=1 to n do
  if b[i]=0 then begin
    Flag := False;
    Break;
  end;

Это кудо, в процедуру Main? Если да то зачем?

Автор: MBo 14.2.2007, 07:14

>в процедуру Main?
Да

> Если да то зачем?
По логике.

Значение счетчика цикла после его исполнения не определено, и использовать его в корыстных целях нельзя.

Автор: FireSnake 14.2.2007, 17:41

MBo, благодарен за помощь, хотя не могу понять почему после выполнения цикла for значения счетчика не определено. Всегда так делал и все было норм.