ТГиК-2019-Лекция-25.11.2019

Тема лекции - алгоритм поиска в ширину и алгоритм поиска в глубину

BFS

Поиск в ширину позволяет найти расстояние до каждой достижимой вершины в графе от исходной вершины .

Пусть задан граф \(G = (V,E) \). Зададим его списком смежности.

• Выберем некую вершину, корень. Обозначим её \(s\)
• Пусть \(colors\) - массив "цветов вершин".
• Цветов всего 3:

1. \(white\) - "вершина не посещена"

2. \( { \color{gray} {gray}} \) - "вершина рассматривается"

3. \( { \color{black} black} \) - "вершина уже просмотрена"

• \(d\) - расстояние от данной вершины до корня
• \(p\) - предок вершины

Замечание: если пути нет, \(d = \infty \mbox{, } d(s)=0 \)

Запишем алгоритм на псевдокоде.

import math

def dfs(adj, s):
    colors = ["white"] * len(adj)
    d = [math.inf] * len(adj)
    p = [-1] * len(adj)

    colors[s] = "gray"
    d[s] = 0
    p[s] = -1

    queue = []
    queue.append(s)

    while len(queue) != 0:
        u = queue.pop(0)

        for v in adj[u]:
            if colors[v] == "white":
                colors[v] = "gray"
                d[v] = d[u] + 1
                p[v] = u

                queue.append(u)
        colors[u] = "black"

Какова же сложность данного алгоритма? Мы просматриваем все вершины и просматриваем все списки смежности. Следовательно, так как при использовании статической очереди добавление и удаление вершин происходят за \(O(1)\), то сложность BFS \(O(|V| + |E|) \)

рис.1. BFS

Схематичное представление BFS

Рассмотрим пошаговую реализацию BFS (рис.1)

Шаг 1. Начинаем с вершины 0. Помечаем её серым (рис.А). Добавляем эту вершину в очередь

Содержимое очереди \( Q = [0] \)

Шаг 2. Вершина 0 просмотрена, помечаем её чёрным, удаляем её из очереди (рис.Б). Перейдём к соседям вершины 0: 1, 2, 3. Помечаем их серым.

Содержимое очереди \( Q = [1, 2, 3] \)

Шаг 3. Переходим конкретно к вершине 1. У неё есть "белый" сосед: 4. Помечаем вершину 1 черным, удаляем её из очереди. Рассматриваем вершину 4, помечаем её серым. (рис.В)

Содержимое очереди \( Q = [2, 3, 4] \)

Шаг 4. У вершины 4 нет "белых" соседей. Значит, возвращаемся назад. Вершина 1 уже чёрная, переходим к вершине 2. У неё есть "белые" соседи: вершины 5 и 6. Помечаем их серым, а вершину 2 помечаем чёрным, она просмотрена (рис.Г)

Содержимое очереди \( Q = [3, 4, 5, 6] \)

Шаг 5. В результате, все вершины просмотрены. Помечаем их все чёрным.

Доказательство BFS

Определим длину кратчайшего пути \(\delta (s,v)\) от \(s\) до \(v\) как минимальное количество ребер на любом из путей от \(s\) к \(v\). Путь длиной \(\delta (s,v)\) от \(s\) к \(v\) называется кратчайшим путем (shortest path) от \(s\) к\(v\) .

Если пути от \(s\) к \(v\) не существует, то \(\delta (s,v) = \infty\) .

Рассмотрим несколько важных свойств, которые пригодятся нам для доказательство того, что поиск в ширину вычисляет длины кратчайших путей.

Лемма 1.

Пусть \(G=(V,E)\) является ориентированным или неориентированным графом и пусть \(s \in V \) — произвольная вершина. Тогда для любого ребра \( (u,v) \in E \) \[ \delta (s,v) \le \delta(s,u) +1 \]

Доказательство

1) Если вершина \(u\) достижима из \(s\), то достижима и вершина \(v\) .

2) В этом случае кратчайший путь из \(s\) в \(v\) не может быть длиннее, чем кратчайший путь из \(s\) в \(u\), за которым следует ребро \((u,v)\). Значит, указанное неравенство выполняется.

3) Если же вершина \(u\) недостижима из \(s\) , то \( \delta (s,v) = \infty \)

4) Получим неравенство \( \infty \le \infty +1 \)

Очевидно, неравенство выполняется и в этом случае.

Вывод: массив \(d\) содержит длины кратчайших путей из \(s\) в остальные вершины, то есть \(d[v]= \delta (s,v)\) .

Лемма 2

Пусть \(G=(V,E)\) является ориентированным или неориентированным графом и пусть процедура BFS выполняется над ним с исходной вершиной \(s \in V \). Тогда по завершении процедуры для каждой вершины \(v \in V \) значение \(d[v]\), вычисленное процедурой BFS, удовлетворяет неравенству \(d[v] \ge \delta (s,v) \)

Доказательство

1) Доказательство проведём по индукции добавления в очередь

2) База индукции: пусть в очереди только одна вершина \(s\). Тогда \(d[s]=0 \ge \delta (s,s)=0 \), то есть, очевидно, неравенство выполняется

3) Шаг индукции.

Пусть для вершины \(u\) известно, что выполняется неравенство \(d[u] \ge \delta (s,u) \)

Тогда по определению массива \( d\) получим \( d[v]=d[u]+1\)

4) По лемме 1 имеем \( \delta (s,v) \le \delta(s,u) +1 \)

5) Соберём всё вместе\[ d[v]=d[u]+1 \ge \delta(s,u) +1 \ge \delta(s,v) \]

Получаем, что \( d[v] \ge \delta(s,v) \)

Лемма 3

Предположим, что во время выполнения процедуры BFS над графом \(G = (V,E) \) очередь Q содержит вершины \( (v_1 , v_2 , ..., v_r)\), где \(v_1\) - голова \(Q\), а \(v_r\) - её хвост. Тогда для всех \( i=1,2,..., r-1 \) выполняется \( d[v_r] \le d[v_1] +1\) и \( d[v_i] \le d[v_{i+1}]+1\)

Доказательство

1) Доказательство проведём по индукции числа операций с очередью

2) База индукции: пусть в очереди содержится только одна вершина \(s\)Очевидно, всё выполняется

3) На каждом шаге индукции необходимо доказать, что лемма выполняется как после помещения вершины в очередь, так и после извлечения ее оттуда.

4) Пусть из очереди извлекается её голова \(v_1\) . Тогда новая голова очереди - \(v_2\)

По определению \(d[v_1] \le d[v_2] \)

Тогда \( d[v_r] \le d[v_1] +1 \le d[v_2] +1 \), а все остальные неравенства не изменяются. Следовательно, лемма справедлива, когда новой головой очереди становится \(v_2\)

5) Пусть

Следствие 4

Если \(v_i\) попадает в \(Q\) до \(v_j\), то \(d[v_i] \le d[v_j] \)

Теорема

Пусть \(\exists G=(V,E)\), к которому применяется \(BFS\). Исходная вершина - \(s\)

• \(BFS\) открывает все вершины, достижимые из \(s\)

• \(d[v]= \delta (s,v) \)

• если \(v \ne s \), то путь от \(s\) к \(v\) содержит путь от \(s\) к \(p[v]\) и ребро \((p[v],v)\)

Доказательство

1) Доказательство проведём от противного. Пусть \(d[v] \ne \delta (s,v) \)

2) Следовательно, \( v \ne s \)

3) Из пункта 2) и леммы 2 \( d[v] > \delta (s,v) \)

4) \(v\) достижимо из \(s\)ю Если бы это было не так, то \( \delta (s,v) = \infty \ge d[v] \)

5) Пусть \(u\) - вершина, непосредственно предшествующая \(v\) на кратчайшем пути от \(s\) к \(v\)\[ \delta (s,v) = \delta (s,u) + 1 \]

6) Так как \( \delta (s,u) < \delta (s,v) \) ,