10 .Поиск в ширину(волновой алгоритм)

Метка вершины – ее расстояние до начальной вершины.

Первой вершине метка 0,смежным с ней – 1, смежным с 1 -2 и тд. С помощью очереди заносим новые вершины (если в буквах) и удаляем те которые уже исследованы.

Трудоемкость – O(n+m)

Применение:

1. Проверка связности графа

2. Распознавание деревьев (дерево – связный граф без циклов)

Утверждение. В графе нет циклов тогда и только тогда, когда в ходе выполнения алгоритма поиска в ширину каждая вершина исследуется на предмет необходимости присвоения ей метки ровно один раз.

Множество вершин графа называется независимым,

если все вершины из этого множества попарно несмежны.

Граф называется двудольным, если множество его

вершин можно разбить на два независимых множества

(доли)

Теорема. Граф является двудольным если и только

если он не содержит циклов нечетной длины