Алгоритмы и структуры данных. Семестр 2. Лекция 1. Графы. 07.09

Что такое граф?
Граф — это структура, представляющая собой набор объектов, в котором некоторые пары объектов в некотором смысле «связаны».
Объекты, называемые вершинами (также называемыми узлами или точками).
Каждая из связанных пар вершин называется ребром.

Что такое граф?
Например:
Вершины (желтые кружки) is V = {1,2,3,4,5}
Ребра (черные линии) это пары вершин, которые связаны. В этом случае ребра :
E = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 4), (4, 5)}
Мы также определяем граф как пару V и E. Если коротко, то G = (V, E).
Мы будем использовать это обозначение.

Что такое граф?
Параллельные вершины :
Два или более ребра, соединяющие одну и ту же пару вершин.
В примере вершины 1 и 2 соединены с 2 ребрами.
Петля
Ребро, которое начинается и заканчивается в одной вершине.

Что такое граф?
Типы графов
Если ребра в графе ориентированы, т. е. указывают только в одном направлении, граф называется ориентированным графом или орграфом.
Если ребра в графе не имеют направления, граф называется неориентированным графом.

Граф, в котором каждое ребро имеет числовой «вес», называется взвешенным графом.
Что такое граф?
Типы графов

Что такое граф?
Терминология
Вершины u и v называются смежными, если u и v соединены некоторым ребром.
Количество ребер, инцидентных вершине, называется степенью вершины или deg(v). Вершина инцидентна ребру, если эта вершина является одной из двух вершин, которые соединяет ребро. Например, град(3) = 3
Листовая вершина — это вершина с deg(v) = 1, например, 5 — листовая вершина.
Изолированная вершина — это вершина с deg(v) = 0 , например, 6 — изолированная вершина.

Что такое граф?
Лемма о рукопожатии

Что такое граф?
Терминология

Графическое представление

Что такое граф?
Представление
Нужно представить график в компьютере.
3 обычных вида представления։
Список ребер
Матрица смежности
Список смежности

Что такое граф?
Представление. Список ребер
Простое перечисление ребер :
Для этого примера список узлов
{1, 2}, {2, 1}
{1, 3}, {3, 1}
{2, 3}, {3, 2}
{2, 5}, {5, 2}
{3, 4}, {4, 3}
Можно использовать 2 массива от и до.
Может использоваться массив пар.

Что такое граф?
Представление: Список смежности

Что такое граф?
Представление։ Матрица смежности
Если между вершинами i и j есть ребро, то (i, j)-я матрица устанавливается в true, а в противном случае - в false:
Для этого примера матрица смежности
Можно использовать массив массивов.

Что такое граф?
Представление. Ориентированный граф
В случае ориентированного графа представление остается прежним, но ребра добавляются только в одном направлении.
Например, матрица соединений для ориентированного графа будет :
Обратите внимание, что для неориентированного графа (i, j) всегда равно (j, i). В случае направленного такого правила нет.

Breadth First Search (BFS)
Поиск в ширину

Breadth First Search (BFS)
BFS также является методом обхода графа.
Алгоритм:
BFS(v)
{
добавить v в очередь q
пока q не пусто
взять первую вершину u из q
удалить первую вершину из q
пометить u как посетившую
для всех непосещенных смежных вершин w из u
добавить w в q
}

Breadth First Search (BFS)
Посещенные вершины : {}
Очередь: {}
Текущая вершина : -
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти
1
2
4
6
7
8
5
3

Breadth First Search (BFS)
Посещенные вершины : {}
Очередь : {1}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1}
Очередь : {}
Текущая вершина : 1
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1}
Очередь : {}
Текущая вершина : 1
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1}
Очередь : {2, 4}
Текущая вершина: 1
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1}
Очередь : {2, 4}
Текущая вершина: 1
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1}
Очередь : {2, 4}
Текущая вершина: -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2}
Очередь : {4}
Текущая вершина : 2
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2}
Очередь : {4}
Текущая вершина : 2
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2}
Очередь : {4, 6, 7}
Текущая вершина : 2
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2}
Очередь : {4, 6, 7}
Текущая вершина : 2
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2}
Очередь : {4, 6, 7}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4}
Очередь : {6, 7}
Текущая вершина : 4
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4}
Очередь : {6, 7}
Текущая вершина: 4
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4}
Очередь : {6, 7, 5}
Текущая вершина: 4
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4}
Очередь : {6, 7, 5}
Текущая вершина : 4
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4}
Очередь : {6, 7, 5}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6}
Очередь : {7, 5}
Текущая вершина : 6
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6}
Очередь : {7, 5}
Текущая вершина : 6
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6}
Очередь : {7, 5}
Текущая вершина : 6
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6}
Очередь : {7, 5}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7}
Очередь : {5}
Текущая вершина : 7
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7}
Очередь : {5}
Текущая вершина : 7
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7}
Очередь : {5, 3}
Текущая вершина : 7
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7}
Очередь : {5, 3}
Текущая вершина : 7
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7}
Очередь : {5, 3}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5}
Очередь : {3}
Текущая вершина : 5
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5}
Очередь : {3}
Текущая вершина : 5
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5}
Очередь : {3, 8}
Текущая вершина : 5
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5}
Очередь : {3, 8}
Текущая вершина : 5
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5}
Очередь : {3, 8}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3}
Очередь : {8}
Текущая вершина : 3
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3}
Очередь : {8}
Текущая вершина : 3
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3}
Очередь : {8}
Текущая вершина : 3
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3}
Очередь : {8}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3, 8}
Очередь : {}
Текущая вершина : 8
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3, 8}
Очередь : {}
Текущая вершина : 8
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3, 8}
Очередь : {}
Текущая вершина : 8
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3, 8}
Очередь : {}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти

Breadth First Search (BFS)
Посещенные вершины : {1, 2, 4, 6, 7, 5, 3, 8}
Очередь : {}
Текущая вершина : -
1
2
4
6
7
8
5
3
Легенда:
Зеленый вершины не посещены
Серый вершины в очереди
Черный вершины посещаются
Оранжевый вершина является текущей вершиной
Голубой стрелки пути по которому мы идем
Красный стрелки - это направление, в котором мы не можем идти