Алгоритмы на графах

1.

6. Алгоритмы на графах
6.1. Обходы графов

2.

Важными задачами теории графов являются задачи
глобального анализа как неориентированных, так и
ориентированных графов. К этим задачам можно отнести:
- задачи поиска циклов или контуров;
- вычисление длин путей между парами вершин;
- перечисление путей с теми или иными свойствами.
Базой для решения многих задач являются алгоритмы
обхода (поиска)
Обход графа – это некоторое перечисление его вершин
(или вершин и ребер). Среди всех обходов наиболее известны
поиск в глубину и поиск в ширину.

3.

6.2. Нахождение деревьев покрытия
(остовов) с помощью алгоритмов поиска в
глубину (ПГ) и поиска в ширину (ПШ)

4.

Поиск в глубину
(англ. depth-first search, DFS)
При данном алгоритме посещается первая вершина, затем
необходимо идти вдоль ребер графа, до попадания в тупик.
Вершина графа является тупиком, если все смежные с ней
вершины уже посещены.
После попадания в тупик нужно возвращаться назад вдоль
пройденного пути, пока не будет обнаружена вершина, у
которой есть еще не посещенная вершина. Затем необходимо
двигаться в этом новом направлении.
Процесс оказывается завершенным при возвращении в
начальную вершину.

5.

6.

Поиск в ширину
(англ. breadth-first search, BFS)
поуровневое
подразумевает
алгоритм
Данный
исследование графа:
вначале посещается корень – произвольно выбранный
узел,
затем – все потомки данного узла, после этого посещаются
потомки потомков и т.д.
Вершины просматриваются в порядке возрастания их
расстояния от корня.

7.

8.

Пример.
Список смежности
N(1) = {2, 6, 7} N(2) = {1, 3, 7}
N(3) = {2, 4, 7} N(4) = {3, 5, 7}
N(5) = {4, 6, 7} N(6) = {1, 5, 7}
N(7) = {1, 2, 3, 4, 5, 6}
2
2
1
6
1
3
7
5
6
4
5
4
3
7

9.

6.3.
Дерево
покрытия
минимального веса
6.3.1. Взвешенный граф
(остов)

10.

Граф
(неориентированный
или
ориентированный)
называется взвешенным, если каждому его ребру или дуге
поставлено в соответствие некоторое число.
Это число называют весом или длиной: w(e) или w(a).
Дерево покрытия (остов) минимального веса – дерево
(остов), сумма весов ребер или дуг которого минимальна по
сравнению с другими деревьями покрытия (остовами).

11.

6.3.2. Задача о
минимального веса
дереве
покрытия

12.

Рассмотрим взвешенный граф G = (V, E), где |V| = n, |E| = m,
каждому ребру графа присвоен вес w(e)
Рассмотрим алгоритм Краскала и алгоритм Прима.

13.

Джозеф Бернерд Краскал (мл.)
(Joseph Bernard Kruskal)
(29 января 1928 – 19 сентября 2010 года)
американский математик, статистик, специалист в
области информатики и психометрии

14.

Роберт Клей Прим
(Robert Clay Prim)
(род. 25 сентября 1921, Техас)
американский ученый-математик и специалист в области
информатики

15.

Алгоритм Краскала
0. Строим пустой граф Оп.
1. Строим граф T1 = On + emin, где emin – ребро минимального
веса графа G.
2. Далее из всех остальных ребер графа G добавляем к
будущему дереву покрытия ребра минимального веса так,
чтобы они не образовывали циклов.

16.

Алгоритм Прима
1. Выбираем ребро минимального веса и строим дерево,
состоящее из этого ребра и двух вершин, инцидентных ему.
2. Затем, рассматриваются рёбра графа, одна вершина
которых уже принадлежит дереву, а другая – нет. Из этих
рёбер выбирается ребро наименьшего веса и добавляется в
будущее дерево покрытия.

17.

Пример.
(7)
G
1
(10)
(12)
6
(22)
(16)
(18)
5
7
2
(14) (19)
(19)
(21)
(17)
4
(11)
3

18.

Пример.
Алгоритм Краскала
0 шаг
(12)
1
(10)
6
(22)
(16)
(7)
(14)
7
(19)
1
(19)
3
2
6
7
3
(17)
(18)
5
2
(11)
4
(21)
5
4
2 шаг
1 шаг
(7)
1
6
(7)
2
7
5
1
3
4
2
(10)
6
5
7
3
4

19.

4 шаг
3 шаг
(7)
1
(10)
6
5
1
(12)
2
7
(11)
6
3
(10)
5
4
(7)
2
7
(11)
3
4
6 шаг
5 шаг
1
(12)
6
(10)
5
(7)
7
(11)
2
(17)
4
1
(12)
3
6
(10)
5
(7)
7
(11)
2
(17)
(19)
3
4
W = 7+10+11+12+17+19=76

20.

Пример.
Алгоритм Прима
1 шаг
2 шаг
3 шаг
(7)
1
(7)
1
2
(10)
4 шаг
(12)
6
1
(10)
2
(12)
7
6
5 шаг
(7)
7
2
(17)
4
(12)
6
1
(10)
(7)
2
7
6 шаг
1
(10)
5
(7)
7
(11)
2
(12)
6
1
(10)
(7)
7
(17)
4
5
(11)
2
(19)
(17)
4
W = 7+10+12+17+11+19=76
3