Списки (окончание). Графы. Лекция 9, 10

План лекции

Очередь
Реализация с помощью списка
Реализация с помощью циклического буфера
Графы
Определения
Вычисление кратчайших расстояний

Очередь

Очередью называется линейный список, в котором все включения производятся на одном

Операции работы с очередью

create(&Q) – создает очередь
makeempty (&Q) – делает очередь Q

Реализация очереди с помощью списка

struct Element { T value; struct Element * next; };
struct Queue

Create, put

void create(Queue *q) { q->front = q->back = NULL; }

void put(Queue *q,

Get, empty

T get(Queue *q)
{
ptrElement p = q->front;
T a = p->value;
q->front =

Реализация очереди с помощью циклического буфера

struct Queue {
T *value; int front; int back; int

Create, put

void create(Queue *q, int size) { q->value = malloc(*q->value*size);
q->front =

Get, empty

T get(Queue *q)
{
T a = q->value[q->front];
q->front = (q->front+1) %

Пример работы с очередью

int main() { Queue Q; create(&Q, 100); put(&Q, 5); put(&Q, 7); while (!empty(Q)) { int b

Дек (double-ended queue) очередь с двумя концами

Деком называется линейный список, в

Графы

Очередь
Реализация с помощью списка
Реализация с помощью циклического буфера
Графы
Определения
Вычисление кратчайших расстояний с

Упорядоченная пара

Пусть А и В – множества
Упорядоченная пара (а, b), состоящая

Декартово произведение

Декартовым произведением АхВ множеств A и B называется множество упорядоченных

Отношения

Пусть А и В —множества
Отношением из А в В называется любое

Виды отношений

Пусть A—множество
Отношение R называется на А
рефлексивным, если аRа для всех

Графы

Графом называется пара (А, R), где А — конечное множество, а

Изображение графов на плоскости

Вершины графа изображают точками
Дуги графа изображают прямо- или

Изображение графов на плоскости

Изображения дуг графа могут пересекаться -- точки пересечения

Дуги графа

Пара (а, b)∈R называется дугой (ребром) графа G
Дуга выходит из

Путь и цикл в графе

Последовательность вершин (а0, а1, ... ,аn), n≥1,

Путь и цикл в графе

A={1, 2, 3, 4}
R = {(1, 1),

Степень вершины

Степенью по входу (полустепенью входа) вершины называется число входящих в

Ациклические графы

Ациклическим графом называется (ориентированный) граф, не имеющий циклов
Вершина, степень по

Дуга и путь в ациклическом графе

Пусть (a, b) – дуга в

Матрица смежностей

Пусть дан граф G = (V,E), N = |V|, M

Матрица инцидентностей

Матрица инцидентностей для графа G – это матрица B размера

Списки смежностей

Списком смежностей для узла v называется список всех узлов w,

Табличное представление списков смежностей

Уменьшает расход памяти, на хранение небольших структур в

Поиск в ширину в графе

Способ нумерации вершин произвольного графа (один из)
Проектирование

Алгоритм поиска в ширину

Пусть дан граф G и выбрана некоторая его

Алгоритм поиска в ширину

BFS (матрица смежности граф G, число вершин n,

Метод поиска в ширину

Метод поиска в ширину

d[2] = 1

d[6] = 1

d[3] = 1

Метод поиска в ширину

d[2] = 1

d[6] = 1

d[3] = 1

d[5] =

Метод поиска в ширину

d[2] = 1

d[6] = 1

d[3] = 1

d[5] =

Метод поиска в ширину

d[2] = 1

d[6] = 1

d[3] = 1

d[5] =