end for

End if

until Æ

Если в алгоритме 7.1 структуры данных T – это стек (LIFO – Last In First Out), то обход называется поиском в глубину. Если T – это очередь (FIFO – First In Last Out), то обход называется поиском в ширину.

Замечание.Это изложение алгоритмов принципиально отличается от распространенных изложений, см. например, [27]. В структуре данных T одновременно может храниться несколько (максимум ) ссылок на вершину u (в классическом изложении – не более чем одна ссылка), однако возвращена вершина будет только единожды, благодаря первой проверке. Кроме того, в этом алгоритме используется только один цвет за счет того, что вершины красятся после извлечения из контейнера, а не перед помещением туда. Наконец, используются две проверки: перед помещением в контейнер T, чтобы не класть уже пройденные вершины, и после извлечения из T чтобы проверить, не была ли эта вершина помещена в контейнер и извлечена ранее.

Пример. В следующей таблице показаны протоколы поиска в глубину и ширину для графа, диаграмма которого приведена на рис. 7.12'. Предполагается, что начальной является вершина 1. Слева в таблице протокол поиска в глубину, а справа – в ширину.

u	T	u	T
	2,4		2,4
	2,5,6		4,3,6
	2,5,2		3,6,5,6
	2,5,3		6,5,6
	2,5		5,6

-	-	-	-

Рисунок 7.12'. Диаграмма графа к примеру обхода в ширину и глубину

…

ТЕОРЕМА. Если граф G связен и конечен, то поиск в ширину и поиск в глубину обходят все вершины по одному разу за время пропорциональное не более чем суммарному числу вершин и ребер.

[Единственность обхода вершины]

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

[Завершаемость алгоритма]

Всего в T может попасть не более 1 + (p – 1) + (p – 2) +…+ 1=1 + p*(p–1)/2 вершин. На каждом шаге одна вершина удаляется из T. Следовательно, алгоритм завершит свою работу не более чем через O( p² ) шагов.

[Обход всех вершин]

…

[Сложность алгоритма]

Вторая строчка выполняется p раз. Цикл выполняется за O(q) (см. 7.3.1). Следовательно, сложность алгоритма O(p+q).

Замечание.Распространенные варианты этих алгоритмов, в которых в структуре данных T одновременно может храниться не более чем одна ссылка на каждую вершину, имеют оценку сложности O(p).

…