ТГиК-2019-Лекция-25.11.2019: различия между версиями
(→BFS) |
|||
| Строка 10: | Строка 10: | ||
1. <math>white</math> - "вершина не посещена" | 1. <math>white</math> - "вершина не посещена" | ||
| − | 2. <math> { \color{gray} {gray}} </math> - "вершина рассматривается" | + | <nowiki>2. <math> { \color{gray} {gray}} </math> - "вершина рассматривается"</nowiki> |
3. <math> { \color{black} black} </math> - "вершина уже просмотрена" | 3. <math> { \color{black} black} </math> - "вершина уже просмотрена" | ||
*<math>d</math> - расстояние от данной вершины до корня | *<math>d</math> - расстояние от данной вершины до корня | ||
| − | *<math> | + | *<math>p</math> - предок вершины |
Замечание: если пути нет, <math>d = \infty \mbox{, } d(s)=0 </math> | Замечание: если пути нет, <math>d = \infty \mbox{, } d(s)=0 </math> | ||
| + | |||
| + | Запишем алгоритм на псевдокоде. <syntaxhighlight lang="python"> | ||
| + | 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" | ||
| + | </syntaxhighlight>Какова же сложность данного алгоритма? Мы просматриваем все вершины и просматриваем все списки смежности. Следовательно, так как при использовании статической очереди добавление и удаление вершин происходят за <math>O(1)</math>, то сложность BFS <math>O(|V| + |E|) </math> | ||
| + | [[Файл:Bfs1.jpg|мини|506x506пкс|рис.1. BFS]] | ||
| + | |||
| + | === Схематичное представление BFS === | ||
| + | Рассмотрим пошаговую реализацию BFS (рис.1) | ||
| + | |||
| + | Шаг 1. Начинаем с вершины 0. Помечаем её серым (рис.А). Добавляем эту вершину в очередь | ||
| + | |||
| + | Содержимое очереди <math> Q = [0] </math> | ||
| + | |||
| + | Шаг 2. Вершина 0 просмотрена, помечаем её чёрным, удаляем её из очереди (рис.Б). Перейдём к соседям вершины 0: 1, 2, 3. Помечаем их серым. | ||
| + | |||
| + | Содержимое очереди <math> Q = [1, 2, 3] </math> | ||
| + | |||
| + | Шаг 3. Переходим конкретно к вершине 1. У неё есть "белый" сосед: 4. Помечаем вершину 1 черным, удаляем её из очереди. Рассматриваем вершину 4, помечаем её серым. (рис.В) | ||
| + | |||
| + | Содержимое очереди <math> Q = [2, 3, 4] </math> | ||
| + | |||
| + | Шаг 4. У вершины 4 нет "белых" соседей. Значит, возвращаемся назад. Вершина 1 уже чёрная, переходим к вершине 2. У неё есть "белые" соседи: вершины 5 и 6. Помечаем их серым, а вершину 2 помечаем чёрным, она просмотрена (рис.Г) | ||
| + | |||
| + | Содержимое очереди <math> Q = [3, 4, 5, 6] </math> | ||
| + | |||
| + | Шаг 5. В результате, все вершины просмотрены. Помечаем их все чёрным. | ||
| + | |||
<br /> | <br /> | ||
Версия 12:50, 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|) \)
Схематичное представление 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. В результате, все вершины просмотрены. Помечаем их все чёрным.
