ТГиК-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) \) , то в силу нашего выбора вершины \(v\) выполняется условие \(d[u] = \delta (s,u) \)

7) Тогда \(d[v] > \delta (s,v) = \delta (s,u) + 1 = d[u] + 1 \)

Получим \( d[v] > d[u] + 1 \)

8) Что происходит, когда из очереди удаляется элемент u? В этот момент вершина \(v\) может быть и белой, и серой, и чёрной

• Если \(v\) - белая, то \( d[v]=d[u]+1\). Получим противоречие с \( d[v] > d[u] + 1 \)
• Если \(v\) - серая

Пусть она окрашена в этот цвет при удалении из очереди некоторой вершины \(w\), которая была удалена ранее вершины \(u\) и для которой выполняется равенство \(d[v] = d[w] + 1 \)

По следствию 4 \(d[w] < d[u] \)

Тогда \( d[v] = d[w] + 1 < d[u] + 1 \)

Получим противоречие с \( d[v] > d[u] + 1 \)

• Если \(v\) - чёрная, то \( d[v] \le d[u] \) - противоречие

9) Так как получили противоречия при всех возможных исходов, \( d[v] = \delta (s,v) \)

10) Процедурой должны быть открыты все достижимые из \(s\) вершины \(v\), потому что, если это не так, для них будет выполняться \( \infty = d[v] > \delta (s,v) \)

11) Для завершения доказательства теоремы заметим, что если \( p[v] = u \), то \( d[v] = d[u] + 1 \) по алгоритму. Следовательно, мы можем получить кратчайший путь из \(s\) в \(v\), взяв кратчайший путь из \(s\) в \(p[v]\), а затем пройдя по ребру \((p[v],v) \)

Дерево поиска в ширину

Процедура BFS строит в процессе обхода графа \(G = (V,E) \) с исходной вершиной \(s\) дерево поиска в ширину \(G_p = (V_p,E_p) \), где\[V_p = \left \{ v \in V : p[v] \ne -1 \right \} \cup \left \{s \right \} \\ E_p = \left \{ (p[v],v) : v \in V_p \setminus {s} \right \} \]

Так как дерево - это связный граф без циклов, то \( |E_p| = |V_p| - 1 \)

DFS

Стратегия поиска в глубину, как следует из ее названия, состоит в том, чтобы идти “в глубь” графа, насколько это возможно. При выполнении поиска в глубину он исследует все ребра, выходящие из вершины, открытой последней, и покидает вершину, только когда не остается неисследованных ребер — при этом происходит “откат” в вершину, из которой была открыта вершина

Дерево поиска в глубину отличается от дерева поиска в ширину. Теперь это \(G_p = (V_p,E_p) \), где \(E_p = \left \{ (p[v],v) : v \in V и p[v] \ne -1 \right \} \)

Для DFS потребуется:

• \(colors\) - массив "цветов вершин" (аналогично BFS)
• \(d[v]\) - время входа в вершину - записывается, когда вершина \(v\) открывается (то есть закрашивается в серый цвет)
• \(f[v]\) - время выхода из вершины\(v\) - вершина становится чёрной

import math

def dfs_visit(G, u, color, p, d, f, time):
    time = time + 1
    d[u] = time
    color[u] = "gray"
    for v in G[u]:
        if color[v] == "white":
            p[v] = u
            time = dfs_visit(G, v, color, p, f, time)
    color[u] = "black"
    time = time + 1
    f[u] = time
    return time

def dfs(G):
    color = ["white"] * len(G)
    d = [math.inf] * len(G)
    f = [math.inf] * len(G)
    p = [-1] * len(G)
    time = 0
    for u in range(len(G)):
        if color[u] == "white":
            time = dfs_visit(G, u, color, p, d, f, time)

Сложность алгоритма \(O(|V|+|E|) \)