Сайдон замечает, что хотя алгоритм может передать маркер в уже посещенную вершину, он обладает лучшей временной сложностью (и сложностью сообщений), чем Алгоритм 6.15, который предотвращает такие нежелательные передачи. Это означает, что на восстановление после ненужных действий может быть затрачено меньше времени и сообщений, чем на их предотвращение. Сайдон оставляет открытым вопрос о том, существует ли DFS-алгоритм, который достигает сложности сообщений классического алгоритма, т.е. 2|E|, и который затрачивает O(N) единиц времени.

6.4.3  Поиск в глубину со знанием соседей

Если процессам известны идентификаторы их соседей, проход листовых ребер можно предотвратить, включив в маркер список посещенных процессов. Процесс p, получая маркер с включенным в него списком L, не передает маркер процессам из L. Переменная usedp[q] не нужна, т.к. если p ранее передал маркер q, то q Î L; см. Алгоритм 6.18.

Теорема 6.36  DFS-алгоритм со знанием соседей является алгоритмом обхода и вычисляет дерево поиска в глубину, используя 2N-2 сообщений за 2N-2 единиц времени.

У этого алгоритма высокая битовая сложность; если w - количество бит, необходимых для представления одного идентификатора, список L может занять до Nw бит; см. Упражнение 6.14.

var  fatherp         : process      init udef ;

Для инициатора (выполняется один раз):

          begin   fatherp := p ;  выбор  q Î Neighp ;

                     send <tlist, {p}>  to q

          end

Для каждого процесса при получении <tlist, L> от q0:

          begin   if  fatherp = udef  then  fatherp := q0 ;

                     if  $q Î Neighp \ L

                          then  begin  выбор  q Î Neighp \ L ;

                                             send < tlist, LÈ{p} >  to q

                                    end

                          else  if  p - инициатор

                                      then  decide

                                      else  send < tlist, LÈ{p} > to fatherp

          end

Алгоритм 6.18 Алгоритм поиска в глубину со знанием соседей.

 6.5  Остальные вопросы

6.5.1  Обзор волновых алгоритмов

В Таблице 6.19 дан список волновых алгоритмов, рассмотренных в этой главе. В столбце «Номер» дана нумерация алгоритмов в главе; в столбце «C/D» отмечено, является ли алгоритм централизованным (C) или децентрализованным (D); столбец «T» определяет, является ли алгоритм алгоритмом обхода; в столбце «Сообщения» дана сложность сообщений; в столбце «Время» дана временная сложность. В этих столбцах N - количество процессов, |E| - количество каналов, D - диаметр сети (в переходах).