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

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску
Строка 71: Строка 71:
 
'''Шаг 5.''' В результате, все вершины просмотрены. Помечаем их все чёрным.  
 
'''Шаг 5.''' В результате, все вершины просмотрены. Помечаем их все чёрным.  
  
== Доказательство BFS ==
+
==Доказательство BFS==
Поиск в ширину позволяет найти
+
Определим длину кратчайшего пути <math>\delta (s,v)</math> от <math>s</math>  до <math>v</math> как минимальное количество ребер на любом из путей от <math>s</math> к <math>v</math>. Путь длиной <math>\delta (s,v)</math> от <math>s</math>  к <math>v</math> называется '''кратчайшим путем (shortest path)''' от  <math>s</math> к<math>v</math>  .
 +
 
 +
Если пути от <math>s</math> к  <math>v</math> не существует, то <math>\delta (s,v) = \infty</math> .
 +
 
 +
Рассмотрим несколько важных свойств, которые пригодятся нам для доказательство того, что поиск в ширину вычисляет длины кратчайших путей.
 +
 
 +
=== Лемма 1. ===
 +
Пусть <math>G=(V,E)</math> является ориентированным или неориентированным графом и пусть <math>s \in V </math> — произвольная вершина. Тогда для любого ребра <math> (u,v) \in E </math> : <math> \delta (u,v) \le \delta(s,u) +1 </math>
 +
 
 +
'''Доказательство'''
 +
 
 +
1) Если вершина <math>u</math> достижима из <math>s</math>, то достижима и вершина <math>v</math> .
 +
 
 +
2) В этом случае кратчайший путь из <math>s</math>  в <math>v</math>  не может быть длиннее, чем кратчайший путь из <math>s</math> в <math>u</math>, за которым следует ребро <math>(u,v)</math>. Значит, указанное неравенство выполняется.
 +
 
 +
3) Если же вершина <math>u</math> недостижима из <math>s</math> , то <math> \delta (s,v) = \infty </math>
 +
 
 +
4) Получим неравенство <math> \infty \le \infty +1 </math>
 +
 
 +
Очевидно, неравенство выполняется и в этом случае.
 +
 
 +
 
 +
<u>Вывод:</u> массив <math>d</math>содержит длины кратчайших путей из<math>s</math> в остальные вершины, то есть <math>d[v]= delta (s,v)</math> .
 +
 
 +
=== Лемма 2 ===
 +
<br />

Версия 13:44, 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 (u,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