Поиск в ширину

Надо перечислить все вершины ориентированного графа, доступные из данной, в порядке увеличения длины пути от нее. (Тем самым мы решим задачу о кратчайших путях, когда цены ребер равны 1 или $+\infty$ .)

$\scriptstyle{\blacktriangleright}$ 9.2.1. Придумать алгоритм решения этой задачи с числом действий не более $C\cdot{}$ (число ребер, выходящих из интересующих нас вершин).

Решение. Эта задача рассматривалась в главе 6, здесь. Здесь мы приведем подробное решение. Пусть num[i] -- количество ребер, выходящих из i, ${\hbox{\tt out[i][1]}},\ldots,{\hbox{\tt out[i][num[i]]}}$ -- вершины, куда ведут ребра. Вот программа, приведенная ранее:

  procedure Доступные (i: integer);
  |   {напечатать все вершины, доступные из i, включая i}
  | var  X: подмножество 1..n;
  |      P: подмножество 1..n;
  |      q, v, w: 1..n;
  |      k: integer;
  begin
  | ...сделать X, P пустыми;
  | writeln (i);
  | ...добавить i к X, P;
  | {(1) P = множество напечатанных вершин; P содержит i;
  |  (2) напечатаны только доступные из i вершины;
  |  (3) X - подмножество P;
  |  (4) все напечатанные вершины, из которых выходит
  |      ребро в ненапечатанную вершину, принадлежат X}
  | while X непусто do begin
  | | ...взять какой-нибудь элемент X в v;
  | | for k := 1 to num [v] do begin
  | | | w := out [v][k];
  | | | if w не принадлежит P then begin
  | | | | writeln (w);
  | | | | добавить w в P;
  | | | | добавить w в X
  | | | end;
  | | end;
  | end;
  end;

Тогда нам было безразлично, какой именно элемент множества X выбирается. Если мы будем считать X очередью (первым пришел -- первым ушел), то эта программа напечатает все вершины, доступные из i, в порядке возрастания их расстояния от i (числа ребер на кратчайшем пути из i). Докажем это.

Обозначим через V(k) множество всех вершин, расстояние которых от i (в описанном смысле) равно k . Имеет место такое соотношение: $\begin{displaymath} V(k+1)\! =\! \hbox{\rm (концы ребер с началами в $V(k)$)} \... ... \!\setminus\! V(1) \!\setminus\! \ldots \!\setminus\! V(k).\end{displaymath}$ Докажем, что для любого $k=0,1,2\ldots$ в ходе работы программы будет такой момент (после очередной итерации цикла while), когда

в очереди стоят все элементы V(k) и только они;
напечатаны все элементы $V(1),\ldots,V(k)$

(Для k=0 -- это состояние перед циклом.) Рассуждая по индукции, предположим, что в очереди скопились все элементы V(k) . Они будут просматриваться в цикле, пока не кончатся (поскольку новые элементы добавляются в конец, они не перемешаются со старыми). Концы ведущих из них ребер, если они уже не напечатаны, печатаются и ставятся в очередь -- то есть все как в записанном выше соотношении для V(k+1) . Так что когда все старые элементы кончатся, в очереди будут стоять все элементы V(k+1) . $\scriptstyle\blacktriangleleft$

pvv
1/8/1999