Доказательство. 1. Единственность обхода вершин

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

2. Завершаем ость алгоритма. Всего в Т может попасть не более р вершин. На каждом шаге одна вершина удаляется из Т. Следовательно, алгоритм завершит работу не более чем через р шагов.

3. Обход всех вершин. От противного. Пусть алгоритм закончил работу, и вершина z не обойдена. Значит, w не попала в Т. Следовательно, она не была отмечена. Отсюда следует, что все вершины, смежные с z, не были обойдены и отмечены. Аналогично, любые вершины, смежные с неотмеченными, сами не отмечены (после завершения алгоритма). Но G связан, значит, существует путь (x, z). Следовательно, вершина x не отмечена. Но она была отмечена на первом шаге.

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

Вход. Граф G=(X,V), заданный матрицей смежности - начальная вершина (не обязательно первый элемент массива).

Выход. Массив Т меток вершин, где каждая метка равна длине пути от x ₀ до x.

Шаг 1.В начале все вершины у нас не отмечены w[x]=0.

Шаг 2. Выбираем вершину с которой начнем обход и помещаем ее в структуру данных Т.

Шаг 3. Отмечаем эту вершину в качестве пройденной w[x]=1.

Шаг 4. Начинаем просматривать смежные с ней вершины, если данную вершину не просматривали (т.е. w[z]=0) то помещаем ее в структуру данных Т, и отмечаем ее как пройденную w[z]=1.

Шаг 5. Обход будем выполнять до тех пор, пока не отметим все вершины.

На рис. 4.37 представлен граф, вершины которого занумерованы согласно очередности, в которой они посещаются в процессе поиска в ширину.

Рис. 4.37