ТГиК-2019-Лекция-25.11.2019: различия между версиями

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску
Строка 97: Строка 97:
  
 
===Лемма 2===
 
===Лемма 2===
Пусть <math>G=(V,E)</math> является ориентированным или неориентированным графом и пусть процедура BFS выполняется над ним с исходной вершиной <math>s \in V </math>. Тогда по завершении процедуры для каждой вершины <math>v \in V </math> значение <math>v[d]</math>, вычисленное процедурой BFS, удовлетворяет неравенству <math>d[v] \ge \delta (s,v) </math>
+
Пусть <math>G=(V,E)</math> является ориентированным или неориентированным графом и пусть процедура BFS выполняется над ним с исходной вершиной <math>s \in V </math>. Тогда по завершении процедуры для каждой вершины <math>v \in V </math> значение <math>d[v]</math>, вычисленное процедурой BFS, удовлетворяет неравенству <math>d[v] \ge \delta (s,v) </math>
  
 
'''Доказательство'''
 
'''Доказательство'''

Версия 14:02, 25 ноября 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