Нелинейные структуры данных. Графы

1. Нелинейные структуры данных. Графы

1

2. Леонард Эйлер

2

3. Задача о кенигсбергских мостах

3

4. Определение: Граф – это упорядоченная пара G=(V,E) множеств, где V – множество вершин, E- множество ребер

A
AB
B
ИНЦИДЕНТНЫ
СМЕЖНЫЕ
4

5.

Пример ориентированного графа
5

6.

Пример неориентированного графа и оргафа
6

7. Полный граф с 6 вершинами

Опр.: Граф, в котором каждая пара вершин смежна,
называется полным
В простом полном графе
n(n-1)/2 ребер
В полном орграфе
n(n-1) ребер
Подграф
7

8.

Опр.: путь из vi в vj это последовательность ребер
vivi+1, vi+1vi+2, ..., vj-1vj
Длина пути – это число ребер в нем.
Опр.: граф называется взвешенным, если каждому ребру
приписано число, называемое весом.
Длина пути 2-5 равна 3
Стоимость пути 2-5 равна 11
8

9.

Опр.: граф называется связным, если всякую пару вершин
можно соединить по крайней мере одним путем.
Опр.: Цикл – это путь, который начинается и заканчивается
в одной и той же вершине.
Опр.: Дерево – это связный ациклический граф .
9

10.

10

11. Примеры взвешенных графов

11

12. Примеры графов

12

13.

Способы
представления
графов
Матрица
примыканий
(смежности)
Если мало ребер, то
матрица будет
содержать много
пустых значений
Список
примыканий
Увеличивается
время получения
информации о
ребре
13

14. Структуры данных для представления графов

1. Матрица примыканий графа G=(V,E)
14

15.

1
2
3
4
5
1
2
3
4
5
1
0
1
1
0
0
1
0
1
1
0
0
2
1
0
1
1
0
2
1
0
0
0
0
3
1
1
0
0
1
3
0
1
0
0
0
4
0
1
0
0
1
4
0
0
1
0
1
5
0
0
1
1
0
5
0
1
0
1
0
15

16. Структуры данных для представления графов

2. Список примыканий графа G=(V,E) с числом
вершин n записывается в виде одномерного
массива длины n, каждый элемент которого
представляет собой ссылку на список вершин,
смежных с соответствующей вершиной графа
16

17.

17

18.

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

19. Обход графов в глубину

123475689
19

20. Рекурсивный алгоритм обхода в глубину

DepthFirstTraversal (G, v)
G граф
v текущий узел
Visit(v)
Mark(v)
for каждого ребра vw графа G do
if вершина w непомечена then
DepthFirstTraversal(G, w)
end if
end for
20

21. Обход графов в ширину

128374569
21

22. Рекурсивный алгоритм обхода в ширину

BreadthFirstTraversal(G, v)
G граф
v текущий узел
Visit(v)
Mark(v)
Enqueue(v)
while очередь непуста do
Dequeue(v)
for каждого ребра vw в графе G do
if вершина w непомечена then
Visit(w)
Mark(w)
Enqueue(w)
end if
end for
end while
22

23.

2
3
1
1 посетили ,
пометили,
поместили в
очередь
удалили 1 из
очереди
удалили 2 из
очереди
удалили 3 из
очереди
2 посетили ,
пометили,
поместили в
очередь
1 уже помечена, Не посещенных
в нее не заходим ребер из 3 нет,
очередь пуста,
алгоритм
останавливается
больше из 1
ребер нет
3 посетили ,
пометили,
поместили в
очередь
больше из 2
ребер нет
23

24.

1
4
2
3
В глубину: 1
2
3
4
В ширину: 1
2
4
3
В глубину: 1 2 5 4 3 6 7
В ширину: 1 2 5 7 4 3 6
24

25.

В глубину: 1 2 3 4 5 6 7 8 9 10 11 12
В ширину: 1 2 6 3 4 7 8 5 9 10 11 12
25

26.

• https://reference.wolfram.com/language/Com
binatorica/guide/GraphAlgorithms.html
26

27. Хоть и Дракула, но тоже граф….

27