ТГиК-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\)

Следствие 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 \mbox{ и } p[v] \ne -1 \right \} \)

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

  • \(color\) - массив "цветов вершин" (аналогично 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|) \)

рис.2. Классификация рёбер

Классификация рёбер

Рёбра деревьев (tree edges)

Это рёбра леса \(G_p\). Ребро \((u,v)\) является ребром дерева, если при исследовании этого ребра была впервые открыта вершина \(v\)

Обратные рёбра (back edges)

Это рёбра \((u,v)\), соединяющие вершину \(u\) с её предком
\(v\) в дереве поиска в глубину. Петли (ребра-циклы), которые могут встречаться в ориентированных графах, рассматриваются как обратные ребра.

Прямые рёбра (forward edges)

Это рёбра \((u,v)\), не являющиеся ребрами дерева и соединяющие вершину \(u\) с её потомком \(v\) в дереве поиска в глубину

Перекрёстные рёбра (cross edges)

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

Алгоритм DFS можно модифицировать так, что он будет классифицировать встречающиеся при работе ребра. Ключевая идея состоит в том, что каждое ребро \((u,v)\) можно классифицировать с помощью цвета вершины \(v\)

  • Если \(v - white\), то \((u,v)\) - ребро дерева
  • Если \(v - gray\), то \((u,v)\) - обратное ребро
  • Если \(v - black\), то \((u,v)\) - прямое или перекрёстное ребро

Топологическая сортировка

рис.3. Пример топологической сортировки

Это линейное упорядочение всех его вершин

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

Для топологической сортировки графа применяется алгоритм поиска в глубину (DFS) (пояснение можно посмотреть здесь)

int n; // число вершин
vector<int> g[MAXN]; // граф
bool used[MAXN];
vector<int> ans;
 
void dfs (int v) {
	used[v] = true;
	for (size_t i=0; i<g[v].size(); ++i) {
		int to = g[v][i];
		if (!used[to])
			dfs (to);
	}
	ans.push_back (v);
}
 
void topological_sort() {
	for (int i=0; i<n; ++i)
		used[i] = false;
	ans.clear();
	for (int i=0; i<n; ++i)
		if (!used[i])
			dfs (i);
	reverse (ans.begin(), ans.end());

Точки сочленения, мосты и двусвязные компоненты

рис.4. Жёлтые вершины - точки сочленения, красные рёбра - мосты, цифры - двусвязные компоненты

Пусть \( G=(V,E) \) - связный неориентированный граф.

Точкой сочленения (articulation point) \(G\) называется вершина, удаление которой делает граф несвязным.

Мостом (bridge) графа \(G\) называется ребро, удаление которого делает граф несвязным.

Двусвязный компонент (biconnected component) графа \(G\) представляет собой максимальное множество ребер, такое что любые два ребра этого множества принадлежат общему простому циклу.

Поиск точек сочленения

Введём новую величину \(up\)

\( up[u] = \begin{cases} d[u] \mbox{ - время захода в вершину u } \\ d[p] \mbox{, причём (u,p) - обратное ребро } \\ up[v] \mbox{, v - потомок u в дереве поиска } \end{cases} \)

Куда вставить \(up\) в DFS?

import math

def dfs_visit(G, u, color, p, d, f, time, up, cutpoints):
    time = time + 1
    d[u] = time
    up[u] = time
    count = 0
    color[u] = "gray"
    for v in G[u]:
        if color[v] == "white":
            p[v] = u
            count += 1
            time = dfs_visit(G, v, color, p, d, f, time, up, cutpoints)
            up[u] = min(up[u], up[v])
            if p[u] != -1 and up[v] >= d[u]:
                if u not in cutpoints:
                    cutpoints.append(u)
        else:
            up[u] = min(up[u], d[v])  
    if p[u] == -1 and count >= 2:
        if u not in cutpoints:
            cutpoints.append(u)
    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
    up = [-1] * len(G)
    cutpoints = []
    for u in range(len(G)):
        if color[u] == "white":
            time = dfs_visit(G, u, color, p, d, f, time, up, cutpoints)

    cutpoints.sort()
    print(cutpoints)

Поиск мостов

\((u,v)\) - мост, если \(u\) - точка сочленения и \(up[v]>d[u]\)

import math

def dfs_visit(G, u, color, p, d, f, time, up, bridges):
    time = time + 1
    d[u] = time
    up[u] = time
    color[u] = "gray"
    for v in G[u]:
        if p[u] == v:
            continue
        if color[v] == "white":
            p[v] = u
            time = dfs_visit(G, v, color, p, d, f, time, up, bridges)
            up[u] = min(up[u], up[v])
            if up[v] > d[u]:
                if (u, v) not in bridges and (v, u) not in bridges:
                    bridges.append((u,v))
        elif color[v] == "gray":
            up[u] = min(up[u], d[v])   
    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
    up = [-1] * len(G)
    bridges = []
    for u in range(len(G)):
        if color[u] == "white":
            time = dfs_visit(G, u, color, p, d, f, time, up, bridges) 
            
    print(bridges)