Поиск в ширину, применяется для решения произвольных задач на графах, требующих соответствующего порядка обхода ("в ширину") графа; раскрашивая пройденные вершины и/или дуги можно управлять порядком и способами обхода (например, однократное или многократное использование дуг и вершин)

Задача Кратчайший маршрут
В стране Б есть N городов, которые соединены M дорогами. По дорогам можно ездить в обоих направлениях. Между двумя городами могут существовать несколько дорог. Мальчик Вася живет в городе с номером 1, и он хочет поехать в город с номером N. Система дорог спроектирована так, что время проезда по каждой дороге одинаковое. Вася просит вас помочь найти кратчайший маршрут из города 1 в город N. Для этого вам необходимо выяснить, какое минимальное количество дорог необходимо проехать, чтобы попасть в желаемый город.

Формат ввода:

N M
X[1] Y[1]
X[2] Y[2]
…
X[M] Y[M]

N – количество городов в стране.
M – количество дорог в стране.
X[i] Y[i] – описание i-ой дороги между городами X и Y.

Ограничения:

2 <= N < = 1000
1 <= M < = 2000

Формат вывода:

Ответ на задачу - минимальное количество дорог, которые необходимо проехать, чтобы попасть в желаемый город.

Пример ввода:

4 4
1 2
2 3
2 4
3 4

Пример вывода:

2

var g:array[1..1000,1..1000] of longint; p,q:array [1..1000] of longint;  i,uk,un,n,m,a,b,v:longint;
begin
 readln(n,m);
 for i:=1 to m do
  begin
   readln(a,b);
   g[a,b]:=g[a,b]+1;
   g[b,a]:=g[b,a]+1;     
  end;
 for i:=1 to n do
  begin
   p[i]:=-1;
   g[i,i]:=0;
  end;
 un:=1;
 uk:=2;
 p[1]:=0;
 q[1]:=1;
 while uk<>un do
  begin
   v:=q[un];
   un:=un+1;
   for i:=1 to n do
    if (g[v,i]>0)and(p[i]=-1) then begin
                                    q[uk]:=i;
                                    uk:=uk+1;
                                    p[i]:=p[v]+1;
                                   end;
  end;
 writeln(p[n]);
end.

Ещё один пример проверки графа на двудольность в ширину.

Банкет

На банкет были приглашены N Очень Важных Персон (ОВП). Были поставлены 2 стола. Столы достаточно большие, чтобы все посетители банкета могли сесть за любой из них. Проблема заключается в том, что некоторые ОВП не ладят друг с другом и не могут сидеть за одним столом. Вас попросили определить, возможно ли всех ОВП рассадить за двумя столами.

Входные данные

В первой строке входного файла INPUT.TXT дано два целых числа: N и M (0 <= N,M <= 100), где N - количество ОВП, а M - количество пар ОВП, которые не могут сидеть за одним столом. В следующих M строках записано по 2 числа - пары ОВП, которые не могут сидеть за одним столом.

Выходные данные

Если способ рассадить ОВП существует, то в выходной файл OUTPUT.TXT выведите YES и NO в противном случае.

Пример

INPUT.TXT

3 2
1 2
1 3

OUTPUT.TXT

YES

__________

Вот основной код

var g:array [1..100,1..100] of longint; p,q:array[1..1000] of longint; un,uk,i,v,n,k,m:longint; f:boolean;
begin
assign(input, 'input.txt'); reset(input);
 assign(output, 'output.txt'); rewrite(output);
 readln(n,m);
 for i:=1 to m do begin
                   readln(v,k);
                   g[v,k]:=1;
                   g[k,v]:=1;
                   end;
 k:=0;
 v:=0;
 for i:=1 to n do g[i,i]:=0;
 un:=1;
 uk:=2;
 q[1]:=1;
 p[1]:=1;
 f:=true;
 while (un<>uk)and(f) do begin
                          v:=q[un];
                          un:=un+1;
                          for i:=1 to n do
                           if g[v,i]=1
                            then if p[i]=p[v]
                                  then f:=false
                                   else if p[i]=0 then begin
                                                        q[uk]:=i;
                                                        uk:=uk+1;
                                                        p[i]:=3-p[v];
                                                       end;
                          end;
 if f=true then writeln('YES')
            else writeln('NO');
end.

Отредактировано Санчоус (2011-10-16 16:36:08)