VPF::DFS. Что не правильно? - Форум программистов

FireSnake

Дата 13.2.2007, 14:25 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 201
Регистрация: 15.9.2006
Где: Украина, Донецк

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

Пишу рекурсивный обход в глубину, но он работает не правильно... не могу понять, почему выгружаясь из рекурсии он в нее не заходит более.
Входные данные
в первое строке количество вершин и количество ребер (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.

Это сообщение отредактировал(а) FireSnake - 13.2.2007, 14:26

MBo

Дата 13.2.2007, 16:22 (ссылка)

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

Загрузка ...

Бывалый

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

Репутация: 5
Всего: 18

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 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 201
Регистрация: 15.9.2006
Где: Украина, Донецк

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

Цитата

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 (ссылка)

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

Загрузка ...

Бывалый

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

Репутация: 5
Всего: 18

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

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

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

FireSnake

Дата 14.2.2007, 17:41 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 201
Регистрация: 15.9.2006
Где: Украина, Донецк

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

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

Это сообщение отредактировал(а) FireSnake - 14.2.2007, 20:43

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